Let \(F\) and \(F’\) be two forests sharing the same vertex set \(V\) such that \(|E(F) \cap E(F’)| = \theta\). By \(F \cup F’\) we denote the graph on \(V\) with edge set \(E(F) \cup E(F’)\). Since both \(F\) and \(F’\) are \(2\)-colorable, we have \(\chi(F \cup F’) \leq 4\). In this paper we will investigate forests for which we can actually obtain this upper bound for the chromatic number. It will turn out that if neither \(F\) nor \(F’\) contain a path of length three then the chromatic number of \(F \cup F’\) is at most three. We will characterize those pairs of forests \(F\) and \(F’\) which both contain a path of length three and for which the chromatic number of \(F \cup F’\) is always at most three. In the case where one of the forests contains a path of length three and the other does not contain a path of length three we obtained only partial results. The problem then seems to be similar to a problem of Erdős which recently has been solved by Fleischner [2] using a theorem of Alon [3].

With Burnside’s lemma as the main tool, we derive a formula for the number of oriented triangle graphs and for the number of such graphs in which all largest cliques are transitively oriented.

This paper deals with \((a, d)\)-antimagic labelings of special graphs called parachutes. After the introduction of the concept of a parachute, the authors succeed in proving the finiteness of two very interesting subsets of the set of all \((a, d)\)-antimagic parachutes by means of a method using the theory of Diophantine equations and other number-theoretical results.

A rooted graph is a pair \((G, x)\), where \(G\) is a simple undirected graph and \(x \in V(G)\). If \(G\) is rooted at \(x\), its \(k\)-th rotation number \(h_k(G, x)\) is the minimum number of edges in a graph \(F\) of order \(|G| + k\) such that for every \(v \in V(F)\) we can find a copy of \(G\) in \(F\) with the root vertex \(x\) at \(v\); any such \(F\) of size \(h_k(G, x)\) is called a minimal graph. In this paper we prove that if \((G, x)\) is a rooted graph with \(d_{G}(x) = d\) then

\[p(G, x)=\lim_{k \to \infty} \frac{h_k(G, x)}{k} \]

exists and satisfies \(d/2 \leq p(G, x) \leq d\), where \(p(G, x)\) is termed the rotation index of \((G, x)\). We obtain the precise value of this parameter for several classes of rooted graphs and describe the asymptotic behaviour of corresponding minimal graphs.

A \(t\)-interval representation \(f\) of a graph \(G\) is a function which assigns to each vertex \(v \in V(G)\) a union of at most \(t\) closed intervals \(I_{v,1}, I_{v,2}, \ldots, I_{v,t}\) on the real line such that \(f(v) \cap f(w) \neq \emptyset\) if and only if \(v, w \in V(G)\) are adjacent. If no real number lies in more than \(r\) intervals of the representation, we say the interval representation has depth \(r\). The least positive integer \(t\) for which there exists a \(t\)-representation of depth \(r\) of \(G\) is called the depth-\(r\) interval number \(i_r(G)\). E. R. Scheinerman proved that \(i_2(K_n) = \lceil \frac{n}{2} \rceil\) for \(n \geq 2\) and that \(\lceil \frac{n-1}{2(r-1)}+\frac{r}{2n} \rceil \leq i_r(K_n) \leq \frac{n}{2r-2}+1+2\lceil log_r n \rceil \). In the following paper, we will see by construction that \(i_3(K_n) = \lceil \frac{n-1}{4}+\frac{3}{2n} \rceil \). If \(n \geq 5\), this is equal to \(\lceil \frac{n}{4} \rceil\). The main theorem is: if \(n \geq r \geq 4\), then \(i_r(K_n) \leq \max \{ \lceil \frac{n-2}{2(r-1)}+\frac{1}{2} \rceil , 2 \}\). The difference between the lower and upper bounds is at most \(1\).

Let \(L\) be a linear form on the Galois field \(\text{GF}(q^{n+1})\) over \(\text{GF}(q)\) (\(n \geq 2\)). We characterize those integers \(s\) coprime to \(v = (q^{n+1}-1)/(q-1)\) such that \(L(x^s)\) is (or is related to) a quadratic form on \(\text{GF}(q^{n+1})\) over \(\text{GF}(q)\). This relates to a conjecture of Games concerning quadrics of the form \(rD\) in \(\text{PG}(n,q)\), where \(D\) is a difference set in the cyclic group \({Z}_v\), acting as a Singer group on the points and hyperplanes of \(\text{PG}(n,q)\). It has been shown that Games’ conjecture does not hold except possibly in the case \(q = 2\): here we establish that it holds exactly when \(q = 2\). We also suggest a new conjecture. Our result for \(q=2\) enables us to prove another conjecture of Games’, concerning \(m\)-sequences with three-valued periodic cross-correlation function.

Let \(G\) be a group acting on a set \(\Omega\). A subset (finite or infinite) \(A \subseteq \Omega\) is called \(k\)-quasi-invariant, where \(k\) is a non-negative integer, if \(|A^g \backslash A| \leq k\) for every \(g \in G\). In previous work of the authors a bound was obtained, in terms of \(k\), on the size of the symmetric difference between a \(k\)-quasi-invariant subset and the \(G\)-invariant subset of \(\Omega\) closest to it. However, apart from the cases \(k = 0, 1\), this bound gave little information about the structure of a \(k\)-quasi-invariant subset. In this paper a classification of \(2\)-quasi-invariant subsets is given. Besides the generic examples (subsets of \(\Omega\) which have a symmetric difference of size at most \(2\) with some \(G\)-invariant subset) there are basically five explicitly determined possibilities.

This note is an extension of \([4]\) , wherein is shown a relation between the dual notions of graceful and edge-graceful graphs. In particular, this note proves two graceful conjectures raised in \([4]\) , and then utilizes the result to edge-gracefully label certain trees not previously known to be edge-graceful.