Pseudo 2-factor isomorphic regular bipartite graphs

被引：6

作者：

Abreu, M. ^{[1
]}

Diwan, A. A. ^{[2
]}

Jackson, Bill ^{[3
]}

Labbate, D. ^{[4
]}

Sheehan, J. ^{[5
]}

机构：

[1] Univ Basilicata, Dipartimento Matemat, I-85100 Potenza, Italy

[2] Indian Inst Technol, Dept Comp Sci & Engn, Bombay 400076, Maharashtra, India

[3] Queen Mary Univ London, Sch Math Sci, London E1 4NS, England

[4] Politecn Bari, Dipartimento Matemat, I-70125 Bari, Italy

[5] Kings Coll London, Dept Math Sci, Old Aberdeen AB24 3UE, Scotland

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 2008年 / 98卷 / 02期

关键词：

2-factor; bipartite; circuits; connectivity;

D O I：

10.1016/j.jctb.2007.08.006

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A graph G is pseudo 2-factor isomorphic if the parity of the number of circuits in a 2-factor is the same for all 2-factors of G. We prove that there exist no pseudo 2-factor isomorphic k-regular bipartite graphs for k >= 4. We also propose a characterization for 3-edge-connected pseudo 2-factor isomorphic cubic bipartite graphs and obtain some partial results towards our conjecture. (C) 2007 Elsevier Inc. All rights reserved.

引用

页码：432 / 442

页数：11

共 12 条

[1] Two results on matching extensions with prescribed and proscribed edge sets [J].

Aldred, REL ;

Holton, DA ;

Porteous, MI ;

Plummer, MD .

DISCRETE MATHEMATICS, 1999, 206 (1-3) :35-43

[2] Regular bipartite graphs with all 2-factors isomorphic [J].

Aldred, REL ;

Funk, M ;

Jackson, B ;

Labbate, D ;

Sheehan, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2004, 92 (01) :151-161

[3]

[Anonymous], 1992, J AM MATH SOC

[4] Short solution of Kotzig's problem for bipartite graphs [J].

Asratian, AS .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1998, 74 (02) :160-168

[5]

ASRATIAN AS, 1991, SOV MATH DOKL, V43, P1

[6]

Biggs N., 1993, Algebraic Graph Theory

[7] Disconnected 2-factors in planar cubic bridgeless graphs [J].

Diwan, AA .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2002, 84 (02) :249-259

[8] On the extremal number of edges in 2-factor Hamiltonian graphs [J].

Faudree, Ralph J. ;

Gould, Ronald J. ;

Jacobson, Michael S. .

GRAPH THEORY IN PARIS: PROCEEDINGS OF A CONFERENCE IN MEMORY OF CALUDE BERGE, 2007, :139-+

[9] 2-Factor hamiltonian graphs [J].

Funk, M ;

Jackson, B ;

Labbate, D ;

Sheehan, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 87 (01) :138-144

[10]

McCuaig W, 2000, J GRAPH THEOR, V35, P46

← 1 2 →