論文の公開元へSufficient conditions for the existence of regular factors in star-free graphs
概要
In this thesis, we study the existence of regular factors in star-free graphs. More
specifically, we are interested in sufficient conditions for the existence of 3-factors
and 1-factors (i.e. perfect matchings) in star-free graphs.
We first give several definitions (for more comprehensive description of definitions of basic terms and symbols in graph theory, the reader is referred to Chapter
2). Our notation is standard, and is mostly taken from Diestel [6]. In this thesis,
we consider only finite undirected graphs with no loops (but possibly with multiple edges). Let G be a graph. We let V (G) and E(G) denote the vertex set and
the edge set of G, respectively. We also let δ(G) denote the minimum degree of
G. For e, f ∈ E(G), let distG (e, f ) denote the length of a shortest V (e) − V (f )
path. Let f be an integer-valued function defined on V (G). A spanning subgraph
F of G such that degF (x) = f (x) for all x ∈ V (G) is called an f -factor of G.
Let r ≥ 1 be an integer. If f (x) = r for all x ∈ V (G), an f -factor is called an
r-regular factor of G or simply an r-factor of G. For an integer k ≥ 1, a graph
G is called k-connected if |V (G)| ≥ k + 1 and G − X is connected for any subset
X ⊆ V (G) with |X| ≤ k − 1. For an integer l, a graph G is called l-edge-connected
if |V (G)| ≥ 2 and G − F is connected for any subset F ⊆ E(G) with |F | ≤ l − 1.
A complete bipartite graph K1,t with partite sets of cardinalities 1 and t is called
a t-star. For a connected graph H, G is called H-free if H is not an induced
subgraph of G. For example, G is K1,t -free or t-star-free if G has no K1,t as an
induced subgraph. ...
