Eulerian subgraphs and Hamilton-connected line graphs
type: Item
instance of: scholarly article
title: Eulerian subgraphs and Hamilton-connected line graphs
zbMATH Open document ID: 1057.05053
author: Dengxin Li
author: Hong-Jian Lai
author: Mingquan Zhan
published in: Discrete Applied Mathematics
publication date: 2005-02-23T00:00:00Z
review text: A graph is super-Eulerian if it has a spanning Eulerian subgraph. A graph \(G\) is Hamilton-connected if for every pair \(u,v\) of distinct vertices of \(G\), there exists a \((u,v)\)-path containing all vertices of \(G\). If \(G\) is a graph, then \(L(G)\) and \(\kappa(G)\) denote the line graph and the connectivity of \(G\), respectively. Let \(C(l,k)\) be the class of 2-edge-connected graphs of order \(n\) such that \(G\in C(l,k)\) if and only if for every edge cut \(S\subseteq E(G)\) with \(| S| \leq 3\), each component of \(G-S\) has order at least \((n-k)/l\). The main results of the authors are the following two theorems. Theorem 1.3. If \(G\in C(6,0)\), then \(G\) is super-Eulerian if and only if \(G\) cannot be contracted to \(K_{2,3}\), \(K_{2,5}\), or \(K_{2,3}(e)\), where \(K_{2.3}(e)\) is obtained from \(K_{2,3}\) by replacing the edge \(e\in E(K_{2,3})\) by a path of length 2. Theorem 1.6. If \(G\in C(6,0)\) and \(n\geq 7\), then \(L(G)\) is Hamilton-connected if and only if \(\kappa(L(G))\geq 3\).
reviewed by: Lutz Volkmann
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 2137491
zbMATH Keywords: super-Eulerian
zbMATH Keywords: Hamilton-connected
zbMATH Keywords: line graph, contraction
MaRDI profile type: Publication
full work available at URL: j.dam.2004.04.005
OpenAlex ID: W2144331024
cites work: Q5422499
cites work: A note on minimum degree conditions for supereulerian graphs
cites work: Q3791179
cites work: A reduction method to find spanning Eulerian subgraphs
cites work: Graphs without spanning closed trails
cites work: Super-Eulerian graphs of minimum degree at least \(4\).
cites work: Q3983243
cites work: Super-Eulerian graphs and the Petersen graph. II
cites work: On Eulerian and Hamiltonian Graphs and Line Graphs
cites work: A Note on Sub-Eulerian Graphs
cites work: Q3751608
DOI: 10.1016/J.DAM.2004.04.005
Recommended article: Eulerian subgraphs containing given vertices and hamiltonian line graphs
Recommended article: Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs
Recommended article: Q3981370
Recommended article: Eulerian subgraphs and \(S\)-connectivity of graphs
Recommended article: On hamiltonian line graphs and connectivity
Recommended article: Q4326202
Recommended article: Hamiltonian cycles in spanning subgraphs of line graphs
Recommended article: Q3751608
Recommended article: Eulerian subgraphs containing given edges
description: scientific article; zbMATH DE number 2137491