摘要:

AbstractA degree factor of a graph is either anr‐factor (regular of degreer) or an [m, n]‐factor (with each degree betweenmandn). In a component factor, each component is a prescribed graph. Both kinds of factors are surveyed, and also corresponding factorizati

ISSN:0364-9024    

DOI:10.1002/jgt.3190090103

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY

摘要:

AbstractWe survey known results on the existence and enumeration of many kinds of 1‐factorizations of the complete graph. We also mention briefly some related questions and topics, as well as application

ISSN:0364-9024    

DOI:10.1002/jgt.3190090104

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY

摘要:

AbstractAn isomorphic factorization of a graph is a decomposition into isomorphic edge‐disjoint subgraphs. A number of new and old open problems on isomorphic factorizations are presented along with some existing related result

ISSN:0364-9024    

DOI:10.1002/jgt.3190090105

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY

摘要:

AbstractA connected graphGis calledt‐tough ift·w(G ‐ S) ⩽ |S|for any subsetSofV(G)withw(G ‐ S)>1, wherew(G‐S) is the number of connected components ofG‐S.We prove that everyk‐tough graph has ak‐factor ifk|G|is even and|G|⩾k+ 1. This result, first conjectured by Chvátal, is sharp in the following sense: For any positive integerkand for any positive real number ε, there existsa (k‐ ε)‐tough graphGwithk|G|even and|G|

ISSN:0364-9024    

DOI:10.1002/jgt.3190090106

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY

摘要:

AbstractGivenr⩾ 3 and 1 ⩽ λ ⩽r, we determine all values ofkfor which everyr‐regular graph with edge‐connectivity λ ha

ISSN:0364-9024    

DOI:10.1002/jgt.3190090107

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY

摘要:

AbstractFor a nonempty graph, G, we define p(G) and r(G) to be respectively the minimum order and minimum degree of regularity among all connected regular graphsHhaving a nontrivial decomposition into subgraphs isomorphic to G. By f(G), we denote the least integer t for which there is a connected regular graph H having a decomposition into t subgraphs isomorphic to G. In this article, the values of these parameters are determined for complete graphs, cycles, and stars. Furthermore, we show that Δ(T) ⩽r(T) ⩽ δ (T) + 1 for every treeT. andr(T) Δ(T) if the maximum degree Δ(T)

ISSN:0364-9024    

DOI:10.1002/jgt.3190090108

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY

摘要:

AbstractRao posed the following conjecture, “Let G be a self‐complementary graph of orderp, π = (d1… dp) be its degree sequence. Then G has a k‐factor if and only if π − k, = (d1 − k, … dP − k) is graphical.” We construct a family of counterexamples for this conject

ISSN:0364-9024    

DOI:10.1002/jgt.3190090109

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY

摘要:

AbstractFor integers a and b, 0 ⩽ a ⩽ a ⩽ b, an [a, b]‐graph G satisties a ⩽ deg(x, G) ⩽ b for every vertex x of G, and an [a, b]‐factor is a spanning subgraph F such that a ⩽ deg(x, F) ⩽ b for every vertex x of F. An [a, b]‐factor is almost‐regular if b = a + 1. A graph is [a, b]‐factorable if its edges can be decomposed into [a, b]‐factors. When both K and t are positive integers and s is a nonnegative integer, we prove that every [(12K + 2)t + 2ks, (12k + 4)t + 2ks]‐graph is [2k,2k + 1]‐factorable. As its corollary, we prove that every [r.r + 1]‐graph with r ⩾ 12k2+ 2k is [2k + 1]‐factorable, which is a partial extension of the two results, on

ISSN:0364-9024    

DOI:10.1002/jgt.3190090110

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY

摘要:

AbstractLetaandbbe integers such that 0 ⩽a⩽b. Then a graphGis called an [a,b]‐graph if a ⩽dG(x) ϵbfor every x ϵV(G), and an [a, b]‐factor of a graph is defined to be its spanning subgraphFsuch thata⩽dF(x) ⩽bfor every vertex x, wheredG(x) anddF(x) denote the degrees of x inGandF, respectively. If the edges of a graph can be decomposed into [a.b]‐factors then we say that the graph is [2a,2a]‐factorable. We prove the following two theorems: (i) a graphGis [2a,2b)‐factorable if and only ifGis a [2am,2bm]‐graph for some integerm, and (ii) every [8m+ 2k, 10m+ 2k]‐

ISSN:0364-9024    

DOI:10.1002/jgt.3190090111

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY

摘要:

AbstractAn orthogonal one‐factorization graph (OOFG) is a graph in which the vertices are one‐factorizations of some underlying graphH, and two vertices are adjacent if and only if the one‐factorizations are orthogonal. An arbitrary finite graph,G, is realizable if there is an OOFG isomorphic toG.We show that every finite graph is realizable as an OOFG with underlying graphKnfor somen.We also discuss some special

ISSN:0364-9024    

DOI:10.1002/jgt.3190090112

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1985

数据来源: WILEY