Almost self-complementary factors of complete bipartite graphs

Dalibor Fronček

doi:10.1016/S0012-365X(96)00237-3

Almost self-complementary factors of complete bipartite graphs

Dalibor Fronček

Mathematics & Statistics

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

3 Scopus citations

Abstract

A complete bipartite graph without one edge, K̃_{n, m}, is called almost complete bipartite graph. A graph K̃_{2n+1, 2m+1} that can be decomposed into two isomorphic factors with a given diameter d is called d-isodecomposable. We prove that K̃_{2n+1, 2m+1} is d-isodecomposable only if d = 3, 4, 5, 6 or ∞ and completely determine all d-isodecomposable almost complete bipartite graphs for each diameter. For d = ∞ we, moreover, present all classes of possible disconnected factors.

Original language	English (US)
Pages (from-to)	317-327
Number of pages	11
Journal	Discrete Mathematics
Volume	167-168
DOIs	https://doi.org/10.1016/S0012-365X(96)00237-3
State	Published - Apr 15 1997

Keywords

Graph decompositions
Isomorphic factors
Self-complementary graphs

Publisher link

10.1016/S0012-365X(96)00237-3

Find It

Find It at U of M Libraries

Cite this

@article{8391d2c015ed44369cc53b5893c15e50,

title = "Almost self-complementary factors of complete bipartite graphs",

abstract = "A complete bipartite graph without one edge, {\~K}n, m, is called almost complete bipartite graph. A graph {\~K}2n+1, 2m+1 that can be decomposed into two isomorphic factors with a given diameter d is called d-isodecomposable. We prove that {\~K}2n+1, 2m+1 is d-isodecomposable only if d = 3, 4, 5, 6 or ∞ and completely determine all d-isodecomposable almost complete bipartite graphs for each diameter. For d = ∞ we, moreover, present all classes of possible disconnected factors.",

keywords = "Graph decompositions, Isomorphic factors, Self-complementary graphs",

author = "Dalibor Fron{\v c}ek",

year = "1997",

month = apr,

day = "15",

doi = "10.1016/S0012-365X(96)00237-3",

language = "English (US)",

volume = "167-168",

pages = "317--327",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Almost self-complementary factors of complete bipartite graphs

AU - Fronček, Dalibor

PY - 1997/4/15

Y1 - 1997/4/15

N2 - A complete bipartite graph without one edge, K̃n, m, is called almost complete bipartite graph. A graph K̃2n+1, 2m+1 that can be decomposed into two isomorphic factors with a given diameter d is called d-isodecomposable. We prove that K̃2n+1, 2m+1 is d-isodecomposable only if d = 3, 4, 5, 6 or ∞ and completely determine all d-isodecomposable almost complete bipartite graphs for each diameter. For d = ∞ we, moreover, present all classes of possible disconnected factors.

AB - A complete bipartite graph without one edge, K̃n, m, is called almost complete bipartite graph. A graph K̃2n+1, 2m+1 that can be decomposed into two isomorphic factors with a given diameter d is called d-isodecomposable. We prove that K̃2n+1, 2m+1 is d-isodecomposable only if d = 3, 4, 5, 6 or ∞ and completely determine all d-isodecomposable almost complete bipartite graphs for each diameter. For d = ∞ we, moreover, present all classes of possible disconnected factors.

KW - Graph decompositions

KW - Isomorphic factors

KW - Self-complementary graphs

UR - https://www.scopus.com/pages/publications/0039382459

UR - https://www.scopus.com/pages/publications/0039382459#tab=citedBy

U2 - 10.1016/S0012-365X(96)00237-3

DO - 10.1016/S0012-365X(96)00237-3

M3 - Article

AN - SCOPUS:0039382459

SN - 0012-365X

VL - 167-168

SP - 317

EP - 327

JO - Discrete Mathematics

JF - Discrete Mathematics

ER -

Almost self-complementary factors of complete bipartite graphs

Abstract

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this