M-alternating Hamilton paths and M-alternating Hamilton cycles

DOI10.1016/J.DISC.2008.08.001zbMATH Open1200.05128arXiv1707.07291OpenAlexW2037463560MaRDI QIDQ1025964FDOQ1025964

Authors: Zan-Bo Zhang, Yueping Li, Dingjun Lou 

Publication date: 23 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We study $M$-alternating Hamilton paths and $M$-alternating Hamilton cycles in a simple connected graph $G$ on $u$ vertices with a perfect matching $M$. Let $G$ be a bipartite graph, we prove that if for any two vertices $x$ and $y$ in different parts of $G$, $d(x)+d(y)gequ/2+2$, then $G$ has an $M$-alternating Hamilton cycle. For general graphs, a condition for the existence of an $M$-alternating Hamilton path starting and ending with edges in $M$ is put forward. Then we prove that if $kappa(G)gequ/2$, where $kappa(G)$ denotes the connectivity of $G$, then $G$ has an $M$-alternating Hamilton cycle or belongs to one class of exceptional graphs. Lou and Yu cite{LY} have proved that every $k$-extendable graph $H$ with $kgequ/4$ is bipartite or satisfies $kappa(H)geq2k$. Combining this result with those we obtain we prove the existence of $M$-alternating Hamilton cycles in $H$.

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

Recommendations

• \(M\)-alternating paths in \(n\)-extendable bipartite graphs
• Graphs with no \(M\)-alternating path between two vertices
• Directed Hamilton cycles in digraphs and matching alternating Hamilton cycles in bipartite graphs
• Hamilton paths in \(n\)-extendable bipartite graphs.
• Hamiltonian cycles in n‐extendable graphs

zbMATH Keywords

connectivityperfect matchingdegree sum\(k\)-extendable\(M\)-alternating cycle\(M\)-alternating path

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cites Work

• Graph theory
• On n-extendable graphs
• TWO THEOREMS IN GRAPH THEORY
• Connectivity of \(k\)-extendable graphs with large \(k\).
• \(M\)-alternating paths in \(n\)-extendable bipartite graphs
• One or two disjoint circuits cover independent edges. Lovász-Woodall conjecture
• Characterizing \(2k\)-critical graphs and \(n\)-extendable graphs

Cited In (8)

• \(M\)-alternating paths in \(n\)-extendable bipartite graphs
• Hamiltonian and long cycles in bipartite graphs with connectivity
• Hamiltonian cycle properties in \(k\)-extendable non-bipartite graphs with high connectivity
• On cycles that alternate through selected sets of vertices
• Graphs with no \(M\)-alternating path between two vertices
• Note on odd path extendable graphs
• Paths and cycles concerning independence edges
• Title not available (Why is that?)

This page was built for publication: M-alternating Hamilton paths and \(M\)-alternating Hamilton cycles

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