The induced subgraph K₂_,₃ in a non-Hamiltonian graphs

2019/06/25 by Heping Jiang, Jiang, Heping
Computer Science · Mathematics · #05C45 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1906.10847

openalex publication_date 2019/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A graph G is a tuple (V, E), where V is the vertex set, E is the edge set. A reduced graph is a graph of deleting non-Hamiltonian edges and smoothing out the redundant vertices of degree 2 on an edge except for leaving only one vertex of degree 2. We denote by I a set of cycles only jointed by inside vertices. |I| is the number of sets I in a graph. We use a norm graph to denote a reduced graph of |I|=1. g is a subgraph obtained by deleting all removable cycles from a basis of a norm graph. In this paper, we show that a norm graph G is non-Hamiltonian, if and only if, g and K₂_,₃ are homeomorphic.

Citations

• A note on the Grinberg condition in the cycle spaces

Related

• Non-Hamilton cycle sets of having solutions and their properties
• Disconnected Forbidden Subgraphs, Toughness and Hamilton Cycles
• A New Property of Hamilton Graphs
• A sharp Ore-type condition for a connected graph with no induced star to have a Hamiltonian path
• A Note on Hamilton Cycles