Loading...
Please wait, while we are loading the content...
A note on arbitrarily vertex decomposable graphs
| Content Provider | Open Access Library (OALib) |
|---|---|
| Author | Antoni Marczyk |
| Abstract | 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$. |
| ISSN | 12329274 |
| Journal | Opuscula Mathematica |
| Publisher | AGH University of Science and Technology |
| Publisher Date | 2006-01-01 |
| Access Restriction | Open |
| Subject Keyword | Traceable graphs Perfect matching Arbitrarily vertex decomposable graphs Independence number |
| Content Type | Text |
| Resource Type | Notes |
| Subject | Mathematics |
