We completely classify the graphs all of whose neighbourhoods of vertices are isomorphic to \(P^k_n\) (\(2 \leq k \leq n\)), where \(P^k_n\) is the \(k\)-th power of the path \(P_n\) of length \(n-1\).

Let \(G\) be a finite group and let \(p_i(G)\) denote the proportion of \((x,y) \in G^2\) for which the set \(\{x^2, xy, yx, y^2\}\) has cardinality \(i\). We show that either \(0 < p_1(G) + p_2(G) \leq \frac{1}{2}\) or \(p_1(G) + p_2(G) = 1\), and that either \(p_4(G) = 0\) or \(\frac{5}{32} \leq p_4(G) < 1\). Each of the preceding inequalities are the best possible.

Using linear algebra over \(\text{GF}(2)\) we supply simple proofs to three parity theorems: Gallai’s partition theorem, the odd-parity cover theorem of Sutner, and generalize the “odd-cycle property” theorem of Manber and Shao to binary matroids.

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.