Supereulerian Graphs with Constraints on the Matching Number and Minimum Degree

被引：2

作者：

Algefari, Mansour J. ^{[1
]}

Lai, Hong-Jian ^{[2
]}

机构：

[1] Qassim Univ, Community Coll, Dept Management & Humanities Sci, Buraydah, Saudi Arabia

[2] West Virginia Univ, Dept Math, Morgantown, WV 26506 USA

来源：

GRAPHS AND COMBINATORICS | 2021年 / 37卷 / 01期

关键词：

Supereulerian graph; Hamiltonian line graph; Matching; Minimum degree; Contraction;

D O I：

10.1007/s00373-020-02229-x

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph is supereulerian if it has a spanning eulerian subgraph. We show that a connected simple graph G with n=vertical bar V(G)vertical bar >= 2 and delta(G)>=alpha '(G) is supereulerian if and only if G not equal K-1,K-n-1 if n is even or G not equal K-2,K-n-2 if n is odd. Consequently, every connected simple graph G with delta(G) >= alpha '(G) has a hamiltonian line graph.

引用

页码：55 / 64

页数：10

共 17 条

[1]

[安明强 An Mingqiang], 2016, [应用数学学报, Acta Mathematicae Applicatae Sinica], V39, P871

[2] Sufficient Conditions for a Digraph to be Supereulerian [J].

Bang-Jensen, Jorgen ;

Maddaloni, Alessandro .

JOURNAL OF GRAPH THEORY, 2015, 79 (01) :8-20

[3] 2 THEOREMS IN GRAPH THEORY [J].

BERGE, C .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1957, 43 (09) :842-844

[4]

Boesch F. T., 1977, J. Graph Theory, V1, P79

[5]

Bondy J. A., 2008, GRAPH THEORY

[6] A REDUCTION METHOD TO FIND SPANNING EULERIAN SUBGRAPHS [J].

CATLIN, PA .

JOURNAL OF GRAPH THEORY, 1988, 12 (01) :29-44

[7] SUPEREULERIAN GRAPHS - A SURVEY [J].

CATLIN, PA .

JOURNAL OF GRAPH THEORY, 1992, 16 (02) :177-196

[8]

CHEN ZH, 1995, COMBINATORICS GRAPH, P53

[9]

Chvatal V., 1972, Discrete Math., V2, P111, DOI DOI 10.1016/0012-365X(72)90079-9

[10] The Chvatal-Erdos condition for supereulerian graphs and the Hamiltonian index [J].

Han, Longsheng ;

Lai, Hong-Jian ;

Xiong, Liming ;

Yan, Huiya .

DISCRETE MATHEMATICS, 2010, 310 (15-16) :2082-2090

← 1 2 →