Star subdivisions and connected even factors in the square of a graph

DOI10.1016/J.DISC.2011.09.004MaRDI QIDQ442370zbMATH OpenOpenAlexFDO

Authors Jan Ekstein, Přemysl Holub, Tomáš Kaiser, Liming Xiong, Shenggui Zhang

Publication date 10 August 2012

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.4825

zbMATH Keywords

2s+1})\)\(S(K_{1connected even factorsquare of a graph

Mathematics Subject Classification ID

Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Abstract: For any positive integer $s$, a $[2,2s]$-factor in a graph $G$ is a connected even factor with maximum degree at most $2s$. We prove that if every induced $S(K_{1,2s+1})$ in a graph $G$ has at least 3 edges in a block of degree at most two, then $G^2$ has a $[2,2s]$-factor. This extends the results of Hendry and Vogler and of Abderrezzak et al.

Recommendations

• Star-cycle factors of graphs
• Star partitions and regularity in graphs
• scientific article; zbMATH DE number 1033810
• Connected even factors in the square of essentially 2-edge-connected graph
• scientific article; zbMATH DE number 4150220
• Star-factorization of the complete bipartite multigraphs
• Structure connectivity and substructure connectivity of star graphs
• Star-factorization of symmetric complete bipartite digraphs
• Strong \(f\)-star factors of graphs
• scientific article; zbMATH DE number 1011069

Cites work

• Chvátal-Erdős conditions for paths and cycles in graphs and digraphs. A survey
• Forbidden subgraphs and hamiitonian properties in the square of a connected graph
• Graph theory
• Induced \(S(K_{1,3})\) and hamiltonian cycles in the square of a graph
• The square of a connected S(K1,3)-free graph is vertex pancyclic
• The square of every two-connected graph is Hamiltonian

Cited in

(6)

• Connected even factors in the square of essentially 2-edge-connected graph
• A neighborhood condition for fractional ID-\([a,b]\)-factor-critical graphs
• Stability number and minimum degree for (a, b, k)-critical graphs
• Stability number and \(k\)-Hamiltonian \([a,b]\)-factors
• The multiplicity of 1-factors in the square of a graph
• Induced claws and existence of even factors of graphs

This page was built for publication: Star subdivisions and connected even factors in the square of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442370)