Cyclability, connectivity and circumference

DOI10.1007/978-3-031-25211-2_20arXiv2211.03095OpenAlexW4318022999MaRDI QIDQ6132541FDOQ6132541

Niranjan Balachandran, Anish Hebbar

Publication date: 17 August 2023

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

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.

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

zbMATH Keywords

circumferenceconnectivitycyclabilityHamiltonicity

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

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