z-logo
Premium
An existence theory for loopy graph decompositions
Author(s) -
Dukes Peter,
Malloch Amanda
Publication year - 2011
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20280
Subject(s) - mathematics , combinatorics , graph , discrete mathematics , simple graph , complement graph , line graph , graph power
Let v≥k≥1 and λ≥0 be integers. Recall that a (v, k, λ) block design is a collection ℬof k‐subsets of a v‐set X in which every unordered pair of elements in X is contained in exactly λ of the subsets in ℬ. Now let G be a graph with no multiple edges. A (v, G, λ) graph design is a collection ℋof subgraphs, each isomoprhic to G, of the complete graph K v such that each edge of K v appears in exactly λof the subgraphs in ℋ. A famous result of Wilson states that for a fixed simple graph G and integer λ, there exists a (v, G, λ) graph design for all sufficiently large integers v satisfying certain necessary conditions. Here, we extend this result to include the case of loops in G. As a consequence, we obtain the asymptotic existence of equireplicate graph designs. Applications of the equireplicate condition are given. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 19:280‐289, 2011

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here