Matching transformation graphs of cubic bipartite plane graphs

Sheng Bau; Michael A. Henning

doi:10.1016/S0012-365X(02)00519-8

Matching transformation graphs of cubic bipartite plane graphs

Sheng Bau, Michael A. Henning

University of KwaZulu-Natal

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

In this paper, we explore some properties of the matching transformation graph of a connected cubic bipartite plane graph G. We prove that if M is any perfect matching of G, then G has at least two disjoint M-alternating faces. This result is sharp in the sense that there are connected cubic bipartite plane graphs which do not have three disjoint M-alternating faces for some perfect matching M. We also show that the matching transformation graph of G is 2-connected.

Original language	English
Pages (from-to)	27-36
Number of pages	10
Journal	Discrete Mathematics
Volume	262
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(02)00519-8
Publication status	Published - 6 Feb 2003
Externally published	Yes

Keywords

Alternating cycles
Connectivity
Cubic graphs
Matching transformation graphs
Perfect matchings

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/S0012-365X(02)00519-8

Cite this

@article{75c38b76b1854b25a6b3096bc916a2ba,

title = "Matching transformation graphs of cubic bipartite plane graphs",

abstract = "In this paper, we explore some properties of the matching transformation graph of a connected cubic bipartite plane graph G. We prove that if M is any perfect matching of G, then G has at least two disjoint M-alternating faces. This result is sharp in the sense that there are connected cubic bipartite plane graphs which do not have three disjoint M-alternating faces for some perfect matching M. We also show that the matching transformation graph of G is 2-connected.",

keywords = "Alternating cycles, Connectivity, Cubic graphs, Matching transformation graphs, Perfect matchings",

author = "Sheng Bau and Henning, {Michael A.}",

year = "2003",

month = feb,

day = "6",

doi = "10.1016/S0012-365X(02)00519-8",

language = "English",

volume = "262",

pages = "27--36",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Matching transformation graphs of cubic bipartite plane graphs

AU - Bau, Sheng

AU - Henning, Michael A.

PY - 2003/2/6

Y1 - 2003/2/6

N2 - In this paper, we explore some properties of the matching transformation graph of a connected cubic bipartite plane graph G. We prove that if M is any perfect matching of G, then G has at least two disjoint M-alternating faces. This result is sharp in the sense that there are connected cubic bipartite plane graphs which do not have three disjoint M-alternating faces for some perfect matching M. We also show that the matching transformation graph of G is 2-connected.

AB - In this paper, we explore some properties of the matching transformation graph of a connected cubic bipartite plane graph G. We prove that if M is any perfect matching of G, then G has at least two disjoint M-alternating faces. This result is sharp in the sense that there are connected cubic bipartite plane graphs which do not have three disjoint M-alternating faces for some perfect matching M. We also show that the matching transformation graph of G is 2-connected.

KW - Alternating cycles

KW - Connectivity

KW - Cubic graphs

KW - Matching transformation graphs

KW - Perfect matchings

UR - http://www.scopus.com/inward/record.url?scp=84867978004&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(02)00519-8

DO - 10.1016/S0012-365X(02)00519-8

M3 - Article

AN - SCOPUS:84867978004

SN - 0012-365X

VL - 262

SP - 27

EP - 36

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Matching transformation graphs of cubic bipartite plane graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this