|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 2 of 14 found articles
| Title: |
A note on arbitrarily vertex decomposable graphs |
| Author: |
Antoni Marczyk |
| Appeared in: |
Opuscula mathematica |
| Paging: | Volume 26 (2006) nr. 1 pages 109-118 |
| Year: |
2006 |
| Contents: |
A graph $G$ of order $n$ is said to be arbitrarily vertex decomposable if for each sequence $(n_{1},\ldots,n_k)$ of positive integers such that $n_{1}+\ldots+n_{k}=n$ there exists a partition $(V_{1},\ldots,V_{k})$ of the vertex set of $G$ such that for each $i \in \{1,\ldots,k\}$, $V_{i}$ induces a connected subgraph of $G$ on $n_i$ vertices.\\ In this paper we show that if $G$ is a two-connected graph on $n$ vertices with the independence number at most $\lceil n/2 \rceil$ and such that the degree sum of any pair of non-adjacent vertices is at least $n-3$, then $G$ is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound $n-3$ is replaced by $n-2$. |
| Publisher: |
AGH University of Science and Technology (provided by DOAJ) |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 2 of 14 found articles
| << previous | next >> |