Cycle decompositions of complete multigraphs

In this paper we establish necessary and sufficient conditions for decomposing the complete multigraph λK_n into cycles of length λ, and the λ‐fold complete symmetric digraph λK into directed cycles of length λ. As a corollary to these results we obtain necessary and sufficient conditions for decomposing λK_n (respectively, λK) into cycles (respectively, directed cycles) of prime length. © 2009 Wiley Periodicals, Inc. J Combin Designs 18: 85–93, 2010     

The spectrum of path factorization of bipartite multigraphs

LetλK_(m,n)be a bipartite multigraph with two partite sets having m and n vertices, respectively.A P_v-factorization ofλK_(m,n)is a set of edge-disjoint P_v-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).When v is an even number,Ushio,Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P_v-factorization ofλK_(m,n).When v is an odd number,we have proposed a conjecture.Very recently,we have proved that the conjecture is true when v=4k-1.In this paper we shall show that the conjecture is true when v = 4k 1,and then the conjecture is true.That is,we will prove that the necessary and sufficient conditions for the existence of a P_(4k 1)-factorization ofλK_(m,n)are(1)2km≤(2k 1)n,(2)2kn≤(2k 1)m,(3)m n≡0(mod 4k 1),(4)λ(4k 1)mn/[4k(m n)]is an integer.     

LOWER BOUNDS ON THE MAXIMUM GENUS OF LOOPLESS MULTIGRAPHS

§ 1　IntroductionThe maximum genusγM(G) of a graph G is the maximum among the genera,which Ghas a cellularembedding on a sphere with k handles.Since any embedding of G has atleastone face,by Euler polyhedral equation,itcan be obtained thatγM(G)≤β(G) / 2 ,whereβ(G) is the Betti number of G.A graph G is called up-embeddable ifγM(G) =β(G) / 2 .[1 ] has showed that thereare atleasttwo edge-disjointspanning trees in G if G is 4 -edge connected.Let T be a span-ning tree of G.An odd …     

Infinitesimal Hopf Algebras and the cd-Index of Polytopes

Infinitesimal bialgebras were introduced by Joni and Rota [JR]. The basic theory of these objects was developed in [Aff1] and [Aff2]. In this paper we present a simple proof of the existence of the cd-index of polytopes, based on the theory of infinitesimal Hopf algebras.For the purpose of this work, the main examples of infinitesimal Hopf algebras are provided by the algebra \ppp of all posets and the algebra k &;lt;ab&;gt; of noncommutative polynomials. We show that k &;lt;ab&;gt; satisfies the following universal property: given a graded infinitesimal bialgebra A and a morphism of algebras ζ _A \colon A→ k , there exists a unique morphism of graded infinitesimal bialgebras ψ\colon A → k&;lt;ab&;gt; such that ζ_{1,0}ψ=ζ_A, where ζ_{1,0} is evaluation at (1,0). When the universal property is applied to the algebra of posets and the usual zeta function ζ_{\ppp}(P)=1, one obtains the \abindex of posets ψ\colon \ppp→k &;lt;ab&;gt;.The notion of antipode is used to define an analog of the Möbius function of posets for more general infinitesimal Hopf algebras than \ppp , and this in turn is used to define a canonical infinitesimal Hopf subalgebra, called the eulerian subalgebra. All eulerian posets belong to the eulerian subalgebra of \ppp . The eulerian subalgebra of k &;lt;ab&;gt; is precisely the algebra spanned by c=a+b and d=ab+ba. The existence of the cd-index of eulerian posets is then an immediate consequence of the simple fact that eulerian subalgebras are preserved under morphisms of infinitesimal Hopf algebras.The theory also provides a version of the generalized Dehn—Sommerville equations for more general infinitesimal Hopf algebras than k &;lt;ab&;gt;.     

Minimum orders of eulerian oriented digraphs with given diameter

A digraph D is oriented if it does not contain 2-cycles.If an oriented digraph D has a directed eulerian path,it is an oriented eulerian digraph.In this paper,when an oriented eulerian digraph D has minimum out-degree 2 and a diameter d,we find the minimum order of D.In addition,when D is 2-regular with diameter 4m(m ≥ 2),we classify the extremal cases.     

Interval Non‐edge‐Colorable Bipartite Graphs and Multigraphs

An edge‐coloring of a graph G with colors is called an interval t‐coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erd?s constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erd?s's counterexample is the smallest (in a sense of maximum degree) known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non‐edge‐colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.