The cyclic matching sequenceability of regular graphs

Daniel Horsley; Adam Mammoliti

doi:10.1002/jgt.22701

The cyclic matching sequenceability of regular graphs

Daniel Horsley, Adam Mammoliti

School of Mathematics

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

Abstract

The cyclic matching sequenceability of a simple graph 𝐺, denoted cms(𝐺), is the largest integer 𝑠s for which there exists a cyclic ordering of the edges of 𝐺 so that every set of 𝑠 consecutive edges forms a matching. In this paper we consider the minimum cyclic matching sequenceability of 𝑘-regular graphs. We completely determine this for 2-regular graphs, and give bounds for 𝑘⩾3.

Original language	English
Pages (from-to)	342-366
Number of pages	25
Journal	Journal of Graph Theory
Volume	98
Issue number	2
DOIs	https://doi.org/10.1002/jgt.22701
Publication status	Published - Sept 2021

Keywords

chromatic index
edge ordering
matching
matching sequenceability

Access to Document

10.1002/jgt.22701

Cite this

@article{98470b3f92f74d1bb7e2f5b9b7e07921,

title = "The cyclic matching sequenceability of regular graphs",

abstract = "The cyclic matching sequenceability of a simple graph 퐺, denoted cms(퐺), is the largest integer 푠s for which there exists a cyclic ordering of the edges of 퐺 so that every set of 푠 consecutive edges forms a matching. In this paper we consider the minimum cyclic matching sequenceability of 푘-regular graphs. We completely determine this for 2-regular graphs, and give bounds for 푘⩾3.",

keywords = "chromatic index, edge ordering, matching, matching sequenceability",

author = "Daniel Horsley and Adam Mammoliti",

note = "Funding Information: This study was supported by Australian Research Council grants DP150100506 and FT160100048. Publisher Copyright: {\textcopyright} 2021 Wiley Periodicals LLC Copyright: Copyright 2021 Elsevier B.V., All rights reserved.",

year = "2021",

month = sep,

doi = "10.1002/jgt.22701",

language = "English",

volume = "98",

pages = "342--366",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "John Wiley & Sons",

number = "2",

}

TY - JOUR

T1 - The cyclic matching sequenceability of regular graphs

AU - Horsley, Daniel

AU - Mammoliti, Adam

N1 - Funding Information: This study was supported by Australian Research Council grants DP150100506 and FT160100048. Publisher Copyright: © 2021 Wiley Periodicals LLC Copyright: Copyright 2021 Elsevier B.V., All rights reserved.

PY - 2021/9

Y1 - 2021/9

N2 - The cyclic matching sequenceability of a simple graph 퐺, denoted cms(퐺), is the largest integer 푠s for which there exists a cyclic ordering of the edges of 퐺 so that every set of 푠 consecutive edges forms a matching. In this paper we consider the minimum cyclic matching sequenceability of 푘-regular graphs. We completely determine this for 2-regular graphs, and give bounds for 푘⩾3.

AB - The cyclic matching sequenceability of a simple graph 퐺, denoted cms(퐺), is the largest integer 푠s for which there exists a cyclic ordering of the edges of 퐺 so that every set of 푠 consecutive edges forms a matching. In this paper we consider the minimum cyclic matching sequenceability of 푘-regular graphs. We completely determine this for 2-regular graphs, and give bounds for 푘⩾3.

KW - chromatic index

KW - edge ordering

KW - matching

KW - matching sequenceability

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

U2 - 10.1002/jgt.22701

DO - 10.1002/jgt.22701

M3 - Article

AN - SCOPUS:85108284102

SN - 0364-9024

VL - 98

SP - 342

EP - 366

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 2

ER -

The cyclic matching sequenceability of regular graphs

Abstract

Keywords

Access to Document

Other files and links

Edge decomposition of dense graphs

Matchings in Combinatorial Structures

Cite this

The cyclic matching sequenceability of regular graphs

Abstract

Keywords

Access to Document

Other files and links

Projects

Edge decomposition of dense graphs

Matchings in Combinatorial Structures

Cite this