CSpace  > 应用数学研究所
Orthogonal matchings revisited
Qu, Cunquan1; Wang, Guanghui1; Yan, Guiying2
AbstractLet G be a graph on n vertices, which is an edge-disjoint union of ms-factors, that is, s regular spanning subgraphs. Alspach first posed the problem that if there exists a matching M of m edges with exactly one edge from each 2-factor. Such a matching is called orthogonal because of applications in design theory. For s = 2, so far the best known result is due to Stong in 2002, which states that if n >= 3m-2, then there is an orthogonal matching. Anstee and Caccetta also asked if there is a matching M of m edges with exactly one edge from each s-factor? They answered yes for s >= 3. In this paper, we get a better bound and prove that if s = 2 and n >= 2 root 2m+4.5 (note that 2 root 2 <= 2.825), then there is an orthogonal matching. We also prove that if s = 1 and n >= 3.2m - 1, then there is an orthogonal matching, which improves the previous bound (3.79m). (C) 2015 Elsevier B.V. All rights reserved.
KeywordRegular graphs Orthogonal matchings Rainbow matchings Factors
Funding ProjectNational Natural Science Foundation of China[11101243] ; National Natural Science Foundation of China[11371355] ; Scientific Research Foundation for the Excellent Middle-Aged and Young Scientists of Shandong Province of China[BS2012SF016] ; Shandong University ; Independent Innovation Foundation of Shandong University[IFYT14012]
WOS Research AreaMathematics
WOS SubjectMathematics
WOS IDWOS:000358459300026
Citation statistics
Document Type期刊论文
Corresponding AuthorWang, Guanghui
Affiliation1.Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China
2.Chinese Acad Sci, Acad Math & Syst Sci, Beijing 10080, Peoples R China
Recommended Citation
GB/T 7714
Qu, Cunquan,Wang, Guanghui,Yan, Guiying. Orthogonal matchings revisited[J]. DISCRETE MATHEMATICS,2015,338(11):2080-2088.
APA Qu, Cunquan,Wang, Guanghui,&Yan, Guiying.(2015).Orthogonal matchings revisited.DISCRETE MATHEMATICS,338(11),2080-2088.
MLA Qu, Cunquan,et al."Orthogonal matchings revisited".DISCRETE MATHEMATICS 338.11(2015):2080-2088.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Qu, Cunquan]'s Articles
[Wang, Guanghui]'s Articles
[Yan, Guiying]'s Articles
Baidu academic
Similar articles in Baidu academic
[Qu, Cunquan]'s Articles
[Wang, Guanghui]'s Articles
[Yan, Guiying]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Qu, Cunquan]'s Articles
[Wang, Guanghui]'s Articles
[Yan, Guiying]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.