Premium
[ a , b ]‐factorization of a graph
Author(s) -
Kano Mikio
Publication year - 1985
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190090111
Subject(s) - combinatorics , mathematics , graph , vertex (graph theory) , discrete mathematics , graph power , graph factorization , line graph
Let a and b be integers such that 0 ⩽ a ⩽ b . Then a graph G is called an [ a , b ]‐graph if a ⩽ d G (x) ϵ b for every x ϵ V (G), and an [a, b]‐factor of a graph is defined to be its spanning subgraph F such that a ⩽ d F (x) ⩽ b for every vertex x, where d G (x) and d F (x) denote the degrees of x in G and F , respectively. If the edges of a graph can be decomposed into [ a.b ]‐factors then we say that the graph is [2 a , 2a ]‐factorable. We prove the following two theorems: (i) a graph G is [2 a , 2b )‐factorable if and only if G is a [2 am,2bm ]‐graph for some integer m , and (ii) every [8 m + 2k, 10 m + 2 k ]‐graph is [1,2]‐factorable.