Cyclability, connectivity and circumference

DOI10.1007/978-3-031-25211-2_20MaRDI QIDQ6132541zbMATH OpenOpenAlexFDO

Authors Niranjan Balachandran, Anish Hebbar

Publication date 17 August 2023

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.03095, https://eprints.iisc.ac.in/81180/1/caldam_2023.pdf

zbMATH Keywords

circumferenceconnectivitycyclabilityHamiltonicity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: In a graph $G$, a subset of vertices $SsubseteqV(G)$ is said to be cyclable if there is a cycle containing the vertices in some order. $G$ is said to be $k$-cyclable if any subset of $kgeq2$ vertices is cyclable. If any $k$ extit{ordered} vertices are present in a common cycle in that order, then the graph is said to be $k$-ordered. We show that when $kleqsqrtn+3$, $k$-cyclable graphs also have circumference $c(G)geq2k$, and that this is best possible. Furthermore when $kleqfrac3n4-1$, $c(G)geqk+2$, and for $k$-ordered graphs we show $c(G)geqminn,2k$. We also generalize a result by Byer et al. on the maximum number of edges in nonhamiltonian $k$-connected graphs, and show that if $G$ is a $k$-connected graph of order $ngeq2(k^2+k)$ with $$, then the graph is hamiltonian, and moreover the extremal graphs are unique.

Cites work

• scientific article; zbMATH DE number 7053391 (Why is no real title available?)
• A look at cycles containing specified elements of a graph
• A method in graph theory
• A note on Hamiltonian circuits
• An Improved Algorithm for Finding Cycles Through Elements
• Cyclability in graph classes
• Edge bounds in nonhamiltonian \(k\)-connected graphs
• Generalizations of Dirac's theorem in Hamiltonian graph theory -- a survey
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• Long cycles in 3-cyclable graphs
• Longest cycles in \(k\)-connected graphs with given independence number
• New families of hypohamiltonian graphs
• Note on Hamilton Circuits
• On maximal paths and circuits of graphs
• Some Theorems on Abstract Graphs
• Survey of results on \(k\)-ordered graphs
• k-ordered Hamiltonian graphs

Cited in

(1)

• Connecting Cycles for Concentric Circles

This page was built for publication: Cyclability, connectivity and circumference

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