Hamiltonicity of complements of middle graphs

被引：1

作者：

An, Xinhui ^{[1
]}

Wu, Baoyindureng ^{[1
]}

机构：

[1] Xinjiang Univ, Coll Math & Syst Sci, Xinjiang 830046, Peoples R China

来源：

DISCRETE MATHEMATICS | 2007年 / 307卷 / 9-10期

关键词：

middle graph; complement; Hamilton cycle;

D O I：

10.1016/j.disc.2006.07.028

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

For a graph G, the middle graph M (G) of G is the graph with vertex set V (G) boolean OR E (G) in which the vertices x and y are joined by an edge if {x, y} boolean AND E (G) not equal 0, and x and y are adjacent or incident in G. In this note, we show that the complement of middle graph M(G) of a graph G is hamiltonian if and only if G is not a star and is not isomorphic to any graph in {K-1, 2K(1), K-2, K-2 boolean OR K-1, K-3, K-3 boolean OR K-1} (c) 2006 Elsevier B.V. All rights reserved.

引用

页码：1178 / 1184

页数：7

共 13 条

[1]

BAUER D, 1982, J COMBIN INFORM SYST, V7, P54

[2]

Bondy J.A., 2008, GRAD TEXTS MATH

[3] Subgraph distances in graphs defined by edge transfers [J].

Chartrand, G ;

Hevia, H ;

Jarrett, EB ;

Schultz, M .

DISCRETE MATHEMATICS, 1997, 170 (1-3) :63-79

[4]

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

[5] HAMILTONIAN TOTAL GRAPHS [J].

FLEISCHNER, H ;

HOBBS, AM .

MATHEMATISCHE NACHRICHTEN, 1975, 68 :59-82

[6] TRAVERSABILITY AND CONNECTIVITY OF MIDDLE GRAPH OF A GRAPH [J].

HAMADA, T ;

YOSHIMURA, I .

DISCRETE MATHEMATICS, 1976, 14 (03) :247-255

[7]

Harary F., 1965, CANAD MATH B, V8, P701, DOI DOI 10.4153/CMB-1965-051-3

[8]

Harary F., 1972, Graph Theory

[9]

Hemminger R.L., 1978, Selected Topics in Graph Theory, P271

[10]

MA G, IN PRESS HAMILTONICI

← 1 2 →