Decomposition of complete bipartite graphs into paths and stars with same number of edges

Tay Woei Shyu

doi:10.1016/j.disc.2012.12.020

Decomposition of complete bipartite graphs into paths and stars with same number of edges

Tay Woei Shyu^*

^*Corresponding author for this work

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

20 Citations (Scopus)

Abstract

In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite graph K_{m, n} into paths P _k+1 and stars S_k+1 with k edges each. In particular, we find necessary and sufficient conditions for accomplishing this when m > k and n ≥ 3k, and we give a complete solution when k = 3. We also apply the results to show that for nonnegative integers p and q and positive integers n and k with n ≥ 4k, there exists a decomposition of the complete graph Kn into p copies of P_k+₁ and q copies of S_k+ ₁ if and only if k(p + q) = (ⁿ₂).

Original language	English
Pages (from-to)	865-871
Number of pages	7
Journal	Discrete Mathematics
Volume	313
Issue number	7
DOIs	https://doi.org/10.1016/j.disc.2012.12.020
Publication status	Published - 2013 Apr 6

Keywords

Complete bipartite graph
Complete graph
Decomposition
Path
Star

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2012.12.020

Cite this

@article{0d756082cf8e41019dd18a8b99d86923,

title = "Decomposition of complete bipartite graphs into paths and stars with same number of edges",

abstract = "In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite graph Km, n into paths P k+1 and stars Sk+1 with k edges each. In particular, we find necessary and sufficient conditions for accomplishing this when m > k and n ≥ 3k, and we give a complete solution when k = 3. We also apply the results to show that for nonnegative integers p and q and positive integers n and k with n ≥ 4k, there exists a decomposition of the complete graph Kn into p copies of Pk+1 and q copies of Sk+ 1 if and only if k(p + q) = (n2).",

keywords = "Complete bipartite graph, Complete graph, Decomposition, Path, Star",

author = "Shyu, {Tay Woei}",

note = "Funding Information: I am so thankful for the referees{\textquoteright} helpful comments. The research was supported by NSC of ROC under grant NSC 97-2115-M-003-006 .",

year = "2013",

month = apr,

day = "6",

doi = "10.1016/j.disc.2012.12.020",

language = "English",

volume = "313",

pages = "865--871",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier BV",

number = "7",

}

TY - JOUR

T1 - Decomposition of complete bipartite graphs into paths and stars with same number of edges

AU - Shyu, Tay Woei

N1 - Funding Information: I am so thankful for the referees’ helpful comments. The research was supported by NSC of ROC under grant NSC 97-2115-M-003-006 .

PY - 2013/4/6

Y1 - 2013/4/6

N2 - In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite graph Km, n into paths P k+1 and stars Sk+1 with k edges each. In particular, we find necessary and sufficient conditions for accomplishing this when m > k and n ≥ 3k, and we give a complete solution when k = 3. We also apply the results to show that for nonnegative integers p and q and positive integers n and k with n ≥ 4k, there exists a decomposition of the complete graph Kn into p copies of Pk+1 and q copies of Sk+ 1 if and only if k(p + q) = (n2).

AB - In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite graph Km, n into paths P k+1 and stars Sk+1 with k edges each. In particular, we find necessary and sufficient conditions for accomplishing this when m > k and n ≥ 3k, and we give a complete solution when k = 3. We also apply the results to show that for nonnegative integers p and q and positive integers n and k with n ≥ 4k, there exists a decomposition of the complete graph Kn into p copies of Pk+1 and q copies of Sk+ 1 if and only if k(p + q) = (n2).

KW - Complete bipartite graph

KW - Complete graph

KW - Decomposition

KW - Path

KW - Star

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

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

U2 - 10.1016/j.disc.2012.12.020

DO - 10.1016/j.disc.2012.12.020

M3 - Article

AN - SCOPUS:84893688111

SN - 0012-365X

VL - 313

SP - 865

EP - 871

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 7

ER -

Decomposition of complete bipartite graphs into paths and stars with same number of edges

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this