Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user2-connected claw-free chordal graphs are cycle extendable
175
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A cycle $C$ of length $k$ in graph $G$ is extendable if there is another cycle $C$ in $G$ with $V(C) subset V(C)$ and length $k+1$. A graph is cycle extendable if every non-Hamiltonian cycle is extendable. In 1990 Hendry conjectured that any Hamiltonian chordal graph (a Hamiltonian graph with no induced cycle of length greater than three) is cycle extendable, and this conjecture has been verified for Hamiltonian chordal graphs which are interval graphs, planar graphs, and split graphs. We prove that any 2-connected claw-free chordal graph is cycle extendable.
rate research
Read More
Suppose that D is an acyclic orientation of a graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let m and M denote the minimum and the maximum of the number of dependent arcs over all acyclic orientations of G. We call G fully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying m <= d <= M. A graph G is called chordal if every cycle in G of length at least four has a chord. We show that all chordal graphs are fully orientable.
A emph{$k$--bisection} of a bridgeless cubic graph $G$ is a $2$--colouring of its vertex set such that the colour classes have the same cardinality and all connected components in the two subgraphs induced by the colour classes have order at most $k$. Ban and Linial conjectured that {em every bridgeless cubic graph admits a $2$--bisection except for the Petersen graph}. In this note, we prove Ban--Linials conjecture for claw--free cubic graphs.
A graph is strongly perfect if every induced subgraph H has a stable set that meets every maximal clique of H. A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The characterization of claw-free graphs that are strongly perfect by a set of forbidden induced subgraphs was conjectured by Ravindra in 1990 and was proved by Wang in 2006. Here we give a shorter proof of this characterization.
The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for $H$-free graphs. If $k$ is fixed, we obtain the $k$-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every $k geq 1$. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of $k$-Disjoint Connected Subgraphs for $H$-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for $H$-free graphs as for Disjoint Paths.
A graph is $ell$-reconstructible if it is determined by its multiset of induced subgraphs obtained by deleting $ell$ vertices. We prove that $3$-regular graphs are $2$-reconstructible.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
