Hamiltonian Cycle Systems Which Are Both Cyclic and Symmetric

The notion of a symmetric Hamiltonian cycle system (HCS) of a graph Γ has been introduced and studied by J. Akiyama, M. Kobayashi, and G. Nakamura [J Combin Des 12 (2004), 39–45] for , by R. A. Brualdi and M. W. Schroeder [J Combin Des 19 (2011), 1–15] for , and then naturally extended by V. Chitra and A. Muthusamy [Discussiones Mathematicae Graph Theory, to appear] to the multigraphs and . In each case, there must be an involutory permutation ψ of the vertices fixing all the cycles of the HCS and at most one vertex. Furthermore, for , this ψ should be precisely the permutation switching all pairs of endpoints of the edges of I. An HCS is cyclic if it is invariant under some cyclic permutation of all the vertices. The existence question for a cyclic HCS of has been completely solved by Jordon and Morris [Discrete Math (2008), 2440–2449]—and we note that their cyclic construction is also symmetric for (mod 8). It is then natural to study the existence problem of an HCS of a graph or multigraph Γ as above which is both cyclic and symmetric. In this paper, we completely solve this problem: in the case of even order, the final answer is that cyclicity and symmetry can always cohabit when a cyclic solution exists. On the other hand, imposing that a cyclic HCS of odd order is also symmetric is very restrictive; we prove in fact that an HCS of with both properties exists if and only if is a prime.     

Characterizations of competition multigraphs

The notion of a competition multigraph was introduced by C. A. Anderson, K. F. Jones, J. R. Lundgren, and T. A. McKee [C. A. Anderson, K. F. Jones, J. R. Lundgren, and T. A. McKee: Competition multigraphs and the multicompetition number, Ars Combinatoria 29B (1990) 185-192] as a generalization of the competition graphs of digraphs.In this note, we give a characterization of competition multigraphs of arbitrary digraphs and a characterization of competition multigraphs of loopless digraphs. Moreover, we characterize multigraphs whose multicompetition numbers are at most m, where m is a given nonnegative integer and give characterizations of competition multihypergraphs.     

Line graphs of multigraphs and Hamilton‐connectedness of claw‐free graphs

We introduce a closure concept that turns a claw‐free graph into the line graph of a multigraph while preserving its (non‐)Hamilton‐connectedness. As an application, we show that every 7‐connected claw‐free graph is Hamilton‐connected, and we show that the well‐known conjecture by Matthews and Sumner (every 4‐connected claw‐free graph is hamiltonian) is equivalent with the statement that every 4‐connected claw‐free graph is Hamilton‐connected. Finally, we show a natural way to avoid the non‐uniqueness of a preimage of a line graph of a multigraph, and we prove that the closure operation is, in a sense, best possible. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:152‐173, 2011     

A Combined Logarithmic Bound on the Chromatic Index of Multigraphs

For a multigraph G, the integer round‐up of the fractional chromatic index provides a good general lower bound for the chromatic index . For an upper bound, Kahn 1996 showed that for any real there exists a positive integer N so that whenever . We show that for any multigraph G with order n and at least one edge, ). This gives the following natural generalization of Kahn's result: for any positive reals , there exists a positive integer N so that + c whenever . We also compare the upper bound found here to other leading upper bounds.     

An Asymptotic Version of the Multigraph 1‐Factorization Conjecture

We give a self‐contained proof that for all positive integers r and all , there is an integer such that for all any regular multigraph of order 2n with multiplicity at most r and degree at least is 1‐factorizable. This generalizes results of Perkovi? and Reed (Discrete Math 165/166 (1997), 567–578) and Plantholt and Tipnis (J London Math Soc 44 (1991), 393–400).     

含偶长圈的7点7边图的图设计

设λKν是ν阶λ重完全图，G是一个无孤立点的有限简单图,λKν的一个G-分拆(或G-设计，记为G-GDλ(ν))是指一个序偶(X，β)，其中X是完全图Kν的顶点集，β是Kν中同构于G的子图(称为区组)的族，使得Kν中每条边恰好出现在β的λ个区组中，本文完全解决了含偶长圈的十个7点7边图的图设计存在性问题。     

On K_(1,k)-factorization of bipartite multigraphs

A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n,which partition the set of edges of λKm,n.In this paper,it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n,whenever k is any positive integer,is that(1) m ≤ kn,(2) n ≤ km,(3) km-n ≡ kn-m ≡ 0(mod(k2-1)) and(4) λ(km-n)(kn-m) ≡ 0(mod k(k -1)(k2 -1)(m n)).     

Decomposing Complete Equipartite Multigraphs into Cycles of Variable Lengths: The Amalgamation‐detachment Approach

Using the technique of amalgamation‐detachment, we show that the complete equipartite multigraph can be decomposed into cycles of lengths (plus a 1‐factor if the degree is odd) whenever there exists a decomposition of into cycles of lengths (plus a 1‐factor if the degree is odd). In addition, we give sufficient conditions for the existence of some other, related cycle decompositions of the complete equipartite multigraph .     

Analyzing local and global properties of multigraphs

The local structure of undirected multigraphs under two random multigraph models is analyzed and compared. The first model generates multigraphs by randomly coupling pairs of stubs according to a fixed degree sequence so that edge assignments to vertex pair sites are dependent. The second model is a simplification that ignores the dependency between the edge assignments. It is investigated when this ignorance is justified so that the simplified model can be used as an approximation, thus facilitating the structural analysis of network data with multiple relations and loops. The comparison is based on the local properties of multigraphs given by marginal distribution of edge multiplicities and some local properties that are aggregations of global properties.