Trade spectra of complete partite graphs

The trade spectrum of a graph G is essentially the set of all integers t for which there is a graph H whose edges can be partitioned into t copies of G in two entirely different ways. In this paper we determine the trade spectrum of complete partite graphs, in all but a few cases.     

Rotation numbers for complete tripartite graphs

Arooted graph is a pair (G, x), whereG is a simple undirected graph andx V(G). IfG is rooted atx, then itsrotation number h(G, x) is the minimum number of edges in a graphF of the same order asG such that for allv V(F), we can find a copy ofG inF with the rootx atv. Rotation numbers for all complete bipartite graphs are now known (see [2], [4], [7]). In this paper we calculate rotation numbers for complete tripartite graphs with rootx in the largest vertex class.Funded by the Science and Engineering Research Council.     

On defining numbers of circular complete graphs

Let d(σ) stand for the defining number of the colouring σ. In this paper we consider and for the onto χ-colourings γ of the circular complete graph K_n,d. In this regard we obtain a lower bound for d^min(K_n,d) and we also prove that this parameter is asymptotically equal to χ-1. Also, we show that when χ?4 and s≠0 then d^max(K_χd-s,d)=χ+2s-3, and, moreover, we prove an inequality relating this parameter to the circular chromatic number for any graph G.     

The competition numbers of complete tripartite graphs

For a graph G, it is known to be a hard problem to compute the competition number k(G) of the graph G in general. In this paper, we give an explicit formula for the competition numbers of complete tripartite graphs.     

Decomposing complete tripartite graphs into 5-cycles when the partite sets have similar size

The problem of finding necessary and sufficient conditions to decompose a complete tripartite graph into 5-cycles was first posed at a conference in 1994 (Mahmoodian and Mirzakhani in Combinatorics Advances, 1995). Since then, many cases of the problem have been solved by various authors; however the case when the partite sets have odd and distinct sizes remains open. In this note, we introduce a new approach to the problem by embedding previously known decompositions into larger ones. Via this approach, we show that when the partite sets have asymptotically similar sizes, the conjectured necessary conditions for a decomposition are also sufficient.     

More rotation numbers for complete bipartite graphs

Let G be a simple undirected graph which has p vertices and is rooted at x. Informally, the rotation number h(G, x) of this rooted graph is the minimum number of edges in a p vertex graph H such that for each vertex v of H, there exists a copy of G in H with the root x at v. In this article we calculate some rotation numbers for complete bipartite graphs, and thus greatly extend earlier results of Cockayne and Lorimer.     

Ramsey numbers for multiple copies of complete graphs

The Ramsey numbers r(m₁K_p, …, m_cK) are calculated to within bounds which are independent of m₁, …, m_c when c > 2 and p₁, …, p_c > 2.     

On the flow numbers of signed complete and complete bipartite graphs

We determine the flow numbers of signed complete and signed complete bipartite graphs.     

Local and mean k-Ramsey numbers for complete graphs

This paper establishes that the local k-Ramsey number R(K_m, k — loc) is identical with the mean k-Ramsey number R(K_m, k — mean). This answers part of a question raised by Caro and Tuza. © 1997 John Wiley & Sons, Inc.     

On ramsey numbers of forests versus nearly complete graphs

A formula is presented for the ramsey number of any forest of order at least 3 versus any graph G of order n ≥ 4 having clique number n - 1. In particular, if T is a tree of order m ≥ 3, then r(T, G) = 1 + (m - 1)(n - 2).     

The signed domatic number of some regular graphs

Let G be a finite and simple graph with vertex set V(G), and let f:V(G)→{−1,1} be a two-valued function. If ∑_x∈N[v]f(x)≥1 for each v∈V(G), where N[v] is the closed neighborhood of v, then f is a signed dominating function on G. A set {f₁,f₂,…,f_d} of signed dominating functions on G with the property that for each x∈V(G), is called a signed dominating family (of functions) on G. The maximum number of functions in a signed dominating family on G is the signed domatic number on G. In this paper, we investigate the signed domatic number of some circulant graphs and of the torus C_p×C_q.     

Covering complete partite hypergraphs by monochromatic components

A well-known special case of a conjecture attributed to Ryser (actually appeared in the thesis of Henderson (1971)) states that $k$-partite intersecting hypergraphs have transversals of at most $k?1$ vertices. An equivalent form of the conjecture in terms of coloring of complete graphs is formulated in Gyárfás (1977): if the edges of a complete graph $K$ are colored with $k$ colors then the vertex set of $K$ can be covered by at most $k?1$ sets, each forming a connected graph in some color. It turned out that the analogue of the conjecture for hypergraphs can be answered: it was proved in Király (2013) that in every $k$-coloring of the edges of the $r$-uniform complete hypergraph $K^r$ ($r\ge 3$), the vertex set of $K^r$ can be covered by at most $?k∕r?$ sets, each forming a connected hypergraph in some color.Here we investigate the analogue problem for complete $r$-uniform $r$-partite hypergraphs. An edge coloring of a hypergraph is called spanning if every vertex is incident to edges of every color used in the coloring. We propose the following analogue of Ryser’s conjecture.In every spanning $(r+t)$-coloring of the edges of a complete $r$-uniform $r$-partite hypergraph, the vertex set can be covered by at most $t+1$ sets, each forming a connected hypergraph in some color.We show that the conjecture (if true) is best possible. Our main result is that the conjecture is true for $1\le t\le r?1$. We also prove a slightly weaker result for $t\ge r$, namely that $t+2$ sets, each forming a connected hypergraph in some color, are enough to cover the vertex set.To build a bridge between complete $r$-uniform and complete $r$-uniform $r$-partite hypergraphs, we introduce a new notion. A hypergraph is complete $r$-uniform $(r,?)$-partite if it has all $r$-sets that intersect each partite class in at most $?$ vertices (where $1\le ?\le r$).Extending our results achieved for $?=1$, we prove that for any $r\ge 3,2\le ?\le r,k\ge 1+r??$, in every spanning $k$-coloring of the edges of a complete $r$-uniform $(r,?)$-partite hypergraph, the vertex set can be covered by at most $1+?\frac{k?r+??1}{?}?$ sets, each forming a connected hypergraph in some color.     

Matchings in complete bipartite graphs and the r-Lah numbers

Czechoslovak Mathematical Journal - We give a graph theoretic interpretation of r-Lah numbers, namely, we show that the r-Lah number $${leftlfloor {matrix{n cr k cr } } rightrfloor _r}$$...