Degree Conditions for Dominating Cycles in 1-tough Graphs

2012/01/30 by Zh. G. Nikoghosyan, Nikoghosyan, Zh. G. · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Limits and Structures in Graph Theory #math.CO

paper · pdf · doi:10.48550/arxiv.1201.6330

27 pages

arxiv created 2012/02/13 · arxiv updated 2012/02/14

Abstract

We prove: (i) if G is a 1-tough graph of order n and minimum degree δ with δ≥(n-2)/3 then each longest cycle in G is a dominating cycle unless G belongs to an easily specified class of graphs with κ(G)=2 and τ(G)=1. The second result follows immediately from the first result: (ii) if G is a 3-connected 1-tough graph with δ≥(n-2)/3 then each longest cycle in G is a dominating cycle.

Cited by

• Hamilton and long cycles in t-tough graphs with t>1

Related

• A Degree Condition for Dominating Cycles in t-tough Graphs with t>1
• Hamilton and long cycles in t-tough graphs with t>1
• Long Cycles in 1-tough Graphs
• A Size Upper Bound for Dominating Cycles
• Toughness and Vertex Degrees