A note on conservative galaxies,Skolem systems,cyclic cycle decompositions,and Heffter arrays

The conservative number of a graph $G$ is the minimum positive integer $M$, such that $G$ admits an orientation and a labeling of its edges by distinct integers in $\{1,2,\dots ,M\}$, such that at each vertex of degree at least three, the sum of the labels on the in-coming edges is equal to the sum of the labels on the out-going edges. A graph is conservative if $M=\left|E\left(G\right)\right|$. It is worth noting that determining whether certain biregular graphs are conservative is equivalent to find integer Heffter arrays.In this work we show that the conservative number of a galaxy (a disjoint union of stars) of size $M$ is $M$ for $M\equiv 0$, $3(mod4)$, and $M+1$ otherwise. Consequently, given positive integers $m_1$, $m_2$, …, $m_n$ with $m_i\ge 3$ for $1\le i\le n$, we construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of infinitely many circulant graphs, generalizing a result of Bryant, Gavlas and Ling (2003). In particular, it allows us to construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of the complete graph $K_{2M+1}$, where $M={\sum }_{i=1}^n{m}_i$. Also, we prove necessary and sufficient conditions for the existence of a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of $K_{2M+2}?F$, where $F$ is a 1-factor. Furthermore, we give a sufficient condition for a subset of ${\mathbb{Z}}_v?\left\{0\right\}$ to be sequenceable.     

Cyclic cycle systems of the complete multipartite graph

In this paper, we study the existence problem for cyclic $?$‐cycle decompositions of the graph $K_m\left[n\right]$, the complete multipartite graph with $m$ parts of size $n$, and give necessary and sufficient conditions for their existence in the case that $2?|\left(m?1\right)n$.     

完全图与完全n部图的完全多部图分解

§ 1　IntroductionLet V(G) and E(G) be the vertex setand the edge setof a graph G,respectively.Fori=1 ,...,p,if V(Gi) V(G) ,E(Gi)∩ E(Gj) = for i≠ j,and∪pi=1 E(Gi) =E(G) ,then wecall{ G1 ,...,GP} a decomposition of G.Let[i,j] be the integer interval including i and j.Let Knbe a complete graph with the vertex set[1 ,n] .For m disjointsubsets A1 ,...Amof[1 ,n] ,let K(A1 ,...,Am) be a complete m-partite graph having partite-sets A1 ,...,Am.If| Ai| =1 ,Ai is called a S-set;otherwi…     

Closed trail decompositions of complete equipartite graphs

The complete equipartite graph $K_m * {\overline{K_n}}$ has mn vertices partitioned into m parts of size n, with two vertices adjacent if and only if they are in different parts. In this paper, we determine necessary and sufficient conditions for the existence of a decomposition of $K_m * {\overline{K_n}}$ into closed trails of length k. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 374–403, 2009     

Resolvable gregarious cycle decompositions of complete equipartite graphs

The complete multipartite graph K_n(m) with n parts of size m is shown to have a decomposition into n-cycles in such a way that each cycle meets each part of K_n(m); that is, each cycle is said to be gregarious. Furthermore, gregarious decompositions are given which are also resolvable.     

Cycle decompositions III: Complete graphs and fixed length cycles

We show that the necessary conditions for the decomposition of the complete graph of odd order into cycles of a fixed even length and for the decomposition of the complete graph of even order minus a 1‐factor into cycles of a fixed odd length are also sufficient. © 2002 John Wiley & Sons, Inc. J Combin Designs 10: 27–78, 2002     

Decomposing complete equipartite graphs into short even cycles

In this article we find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both even and short relative to the number of parts. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:131‐143, 2011     

A tripling construction for mutually orthogonal symmetric hamiltonian double Latin squares

We provide two new constructions for pairs of mutually orthogonal symmetric hamiltonian double Latin squares. The first is a tripling construction, and the second is derived from known constructions of hamilton cycle decompositions of when is prime.     

Equipartite gregarious 6- and 8-cycle systems

A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite gregarious 3-cycle systems are 3-GDDs, and necessary and sufficient conditions for their existence are known (see for instance the CRC Handbook of Combinatorial Designs, 1996, C.J. Colbourn, J.H. Dinitz (Eds.), Section III 1.3). The cases of equipartite and of almost equipartite 4-cycle systems were recently dealt with by Billington and Hoffman. Here, for both 6-cycles and for 8-cycles, we give necessary and sufficient conditions for existence of a gregarious cycle decomposition of the complete equipartite graph K_n(a) (with n parts, n?6 or n?8, of size a).     

Symmetric Hamilton cycle decompositions of the complete graph

We construct a new symmetric Hamilton cycle decomposition of the complete graph K_n for odd n > 7. © 2003 Wiley Periodicals, Inc.     

Cyclic even cycle systems of the complete graph

In this article, it is proved that for each even integer m?4 and each admissible value n with n>2m, there exists a cyclic m‐cycle system of K_n, which almost resolves the existence problem for cyclic m‐cycle systems of K_n with m even. © 2011 Wiley Periodicals, Inc. J Combin Designs 20:23–39, 2012     

A Construction of a perfect set of Euler tours of K2k+1

In this article we prove Kotzig's Conjecture by constructing a perfect set of Euler tours of K_2k+1. As a corollary, we deduce that L(K_2k+1), the line graph of K_2k+1, has a Hamilton decomposition. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 215–230, 1997     

完全多部图同构于二面体群的Cayley齐次分解

设Γ=K_(s[t])是一个完全多部图,其中st是一个偶数,则存在一个二面体群R=D_(2n)(n=st/2),使得R能构造出一个同构于K_(s[t])的Cayley图.讨论了当s、t满足什么条件时,完全多部图Γ有同构于Cay(R,S)的齐次分解.     

Some results on cyclic interval edge colorings of graphs

A proper edge coloring of a graph G with colors is called a cyclic interval t‐coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree admits a cyclic interval ‐coloring if for every vertex v the degree satisfies either or . We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for ‐biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)‐biregular graphs as well as all ‐biregular () graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.     

纠错组码的一个界

给出了完全多部图覆盖与纠错组码的一种一一对应关系，从而利用Huang（1996）的一个结果给出了纠错组码的一个界，并利用仿射设计给出了使这个界的等号成立的一族线性码．