Browsing by Subject "arbitrarily vertex decomposable graphs"

Now showing 1 - 3 of 3

Access status: Open Access ,
A note on arbitrarily vertex decomposable graphs
(2006) Marczyk, Antoni
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$.
Access status: Open Access ,
On some families of arbitrarily vertex decomposable spiders
(Wydawnictwa AGH, 2010) Juszczyk, Tomasz; Zioło, Irmina Anna
A graph $G$ of order n is called arbitrarily vertex decomposable if for each sequence $(n_{1}...,n_{k})$ of positive integers such that $\Sigma^{k}_{i=1}n_{i}=n$, there exists a partition $(V_{1},...,V_{k})$ of the vertex set of G such that for every $i\in{1,....,k}$ the set $V_{i}$ induces a connected subgraph of $G$ on $n_{i}$ vertices. A spider is a tree with one vertex of degree at least 3. We characterize two families of arbitrarily vertex decomposable spiders which are homeomorphic to stars with at most four hanging edges.
Access status: Open Access ,
Recursively arbitrarily vertex-decomposable suns
(2011) Baudon, Olivier; Gilbert, Frédéric; Woźniak, Mariusz
A graph $G = (V,E)$ is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to $|V|$, there is a sequence of vertex-disjoint subsets of $V$ whose orders are given by $\tau$, and which induce connected graphs. The aim of this paper is to study the recursive version of this problem on a special class of graphs called suns. This paper is a complement of [O. Baudon, F. Gilbert, M. Woźniak, Recursively arbitrarily vertex-decomposable graphs, research report, 2010].