Induced path factors of regular graphs

Saieed Akbari; Daniel Horsley; Ian M. Wanless

doi:10.1002/jgt.22654

Induced path factors of regular graphs

Saieed Akbari, Daniel Horsley, Ian M. Wanless

School of Mathematics

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

Abstract

An induced path factor of a graph (Formula presented.) is a set of induced paths in (Formula presented.) with the property that every vertex of (Formula presented.) is in exactly one of the paths. The induced path number (Formula presented.) of (Formula presented.) is the minimum number of paths in an induced path factor of (Formula presented.). We show that if (Formula presented.) is a connected cubic graph on (Formula presented.) vertices, then (Formula presented.). Fix an integer (Formula presented.). For each (Formula presented.), define (Formula presented.) to be the maximum value of (Formula presented.) over all connected (Formula presented.) -regular graphs (Formula presented.) on (Formula presented.) vertices. As (Formula presented.) with (Formula presented.) even, we show that (Formula presented.) exists. We prove that (Formula presented.) and (Formula presented.) and that (Formula presented.) for (Formula presented.).

Original language	English
Pages (from-to)	260-280
Number of pages	21
Journal	Journal of Graph Theory
Volume	97
Issue number	2
DOIs	https://doi.org/10.1002/jgt.22654
Publication status	Published - Jun 2021

Keywords

covering
induced path
path factor
regular graph
subcubic graph

Access to Document

10.1002/jgt.22654

Cite this

@article{75d68b01bba6402ebaa9504462392399,

title = "Induced path factors of regular graphs",

abstract = "An induced path factor of a graph (Formula presented.) is a set of induced paths in (Formula presented.) with the property that every vertex of (Formula presented.) is in exactly one of the paths. The induced path number (Formula presented.) of (Formula presented.) is the minimum number of paths in an induced path factor of (Formula presented.). We show that if (Formula presented.) is a connected cubic graph on (Formula presented.) vertices, then (Formula presented.). Fix an integer (Formula presented.). For each (Formula presented.), define (Formula presented.) to be the maximum value of (Formula presented.) over all connected (Formula presented.) -regular graphs (Formula presented.) on (Formula presented.) vertices. As (Formula presented.) with (Formula presented.) even, we show that (Formula presented.) exists. We prove that (Formula presented.) and (Formula presented.) and that (Formula presented.) for (Formula presented.).",

keywords = "covering, induced path, path factor, regular graph, subcubic graph",

author = "Saieed Akbari and Daniel Horsley and Wanless, {Ian M.}",

year = "2021",

month = jun,

doi = "10.1002/jgt.22654",

language = "English",

volume = "97",

pages = "260--280",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "John Wiley & Sons",

number = "2",

}

TY - JOUR

T1 - Induced path factors of regular graphs

AU - Akbari, Saieed

AU - Horsley, Daniel

AU - Wanless, Ian M.

PY - 2021/6

Y1 - 2021/6

N2 - An induced path factor of a graph (Formula presented.) is a set of induced paths in (Formula presented.) with the property that every vertex of (Formula presented.) is in exactly one of the paths. The induced path number (Formula presented.) of (Formula presented.) is the minimum number of paths in an induced path factor of (Formula presented.). We show that if (Formula presented.) is a connected cubic graph on (Formula presented.) vertices, then (Formula presented.). Fix an integer (Formula presented.). For each (Formula presented.), define (Formula presented.) to be the maximum value of (Formula presented.) over all connected (Formula presented.) -regular graphs (Formula presented.) on (Formula presented.) vertices. As (Formula presented.) with (Formula presented.) even, we show that (Formula presented.) exists. We prove that (Formula presented.) and (Formula presented.) and that (Formula presented.) for (Formula presented.).

AB - An induced path factor of a graph (Formula presented.) is a set of induced paths in (Formula presented.) with the property that every vertex of (Formula presented.) is in exactly one of the paths. The induced path number (Formula presented.) of (Formula presented.) is the minimum number of paths in an induced path factor of (Formula presented.). We show that if (Formula presented.) is a connected cubic graph on (Formula presented.) vertices, then (Formula presented.). Fix an integer (Formula presented.). For each (Formula presented.), define (Formula presented.) to be the maximum value of (Formula presented.) over all connected (Formula presented.) -regular graphs (Formula presented.) on (Formula presented.) vertices. As (Formula presented.) with (Formula presented.) even, we show that (Formula presented.) exists. We prove that (Formula presented.) and (Formula presented.) and that (Formula presented.) for (Formula presented.).

KW - covering

KW - induced path

KW - path factor

KW - regular graph

KW - subcubic graph

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

U2 - 10.1002/jgt.22654

DO - 10.1002/jgt.22654

M3 - Article

AN - SCOPUS:85097771974

VL - 97

SP - 260

EP - 280

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

IS - 2

ER -

Induced path factors of regular graphs

Abstract

Keywords

Access to Document

Other files and links

Edge decomposition of dense graphs

Matchings in Combinatorial Structures

Cite this

Induced path factors of regular graphs

Abstract

Keywords

Access to Document

Other files and links

Projects

Edge decomposition of dense graphs

Matchings in Combinatorial Structures

Cite this