We consider two seemingly related problems. The first concerns pairs of graphs \(G\) and \(H\) containing endvertices (vertices of degree \(1\)) and having the property that, although they are not isomorphic, they have the same collection of endvertex-deleted subgraphs.

The second question concerns graphs \(G\) containing endvertices and having the property that, although no two endvertices are similar, any two endvertex-deleted subgraphs of \(G\) are isomorphic.

A graph \(G\) is supereulerian if it contains a spanning eulerian subgraph. Let \(n\), \(m\), and \(p\) be natural numbers, \(m, p \geq 2\). Let \(G\) be a \(2\)-edge-connected simple graph on \(n > p + 6\) vertices containing no \(K_{m+1}\). We prove that if

\[|E(G)\leq \binom{n-p+1-k}{2}+(m-1)\binom{k+1}{2}+2p-4, \quad (1)]\

where \(k = \lfloor\frac{n-p+1}{m}\rfloor\), then either \(G\) is supereulerian, or \(G\) can be contracted to a non-supereulerian graph of order less than \(p\), or equality holds in (1) and \(G\) can be contracted to \(K_{2,p-2}\) (p is odd) by contracting a complete \(m\)-partite graph \(T_{m,n-p+1}\) of order \(n – p + 1\) in \(G\). This is a generalization of the previous results in [3] and [5].

Steiner triple systems admitting automorphisms whose disjoint cyclic decomposition consist of two cycles are explored. We call such systems bicyclic . Several necessary conditions are given. Sufficient conditions are given when the length of the smaller cycle is \(7\).

The \(\Delta\)-subgraph \(G_\Delta \) of a simple graph \(G\) is the subgraph induced by the vertices of maximum degree of \(G\). In this paper, we obtain some results about the construction of a graph \(G\) if the graph \(G\) is Class 2 and the structure of \(G_\Delta \) is particularly simple.

The automorphism group of a graph acts on its cocycle space over any field. The orbits of this group action will be counted in case of finite fields. In particular, we obtain an enumeration of non-equivalent edge cuts of the graph.

We give necessary and sufficient conditions on the order of a Steiner triple system admitting an automorphism \(\pi\), consisting of \(1\) large cycle, several cycles of length \(4\) and a fixed point.

A graph \(G = (V, E)\) is said to be elegant if it is possible to label its vertices by an injective mapping \(g\) into \(\{0, 1, \dots, |E|\}\) such that the induced labeling \(h\) on the edges defined for edge \(x, y\) by \(h(x, y) = g(x) + g(y) \mod (|E| + 1)\) takes all the values in \(\{1, \dots, |E|\}\). In the first part of this paper, we prove the existence of a coloring of \(K_n\) with a omnicolored path on \(n\) vertices as subgraph, which had been conjectured by Hastman [2].
In the second part we prove that the cycle on \(n\) vertices is elegant if and only if \(n \neq 1 \pmod{4}\) and we give a new construction of an elegant labeling of the path \(P_n\), where \(n \neq 4\).

A round robin tournament on \(q\) players in which draws are not permitted is said to have property \(P(n, k)\) if each player in any subset of \(n\) players is defeated by at least \(k\) other players. We consider the problem of determining the minimum value \(F(n, k)\) such that every tournament of order \(q \geq F(n, k)\) has property \(P(n, k)\). The case \(k = 1\) has been studied by Erdős, G. and E. Szekeres, Graham and Spencer, and Bollobás. In this paper we present a lower bound on \(F(n, k)\) for the case of Paley tournaments.

Upper and lower bounds are established for the toughness of the generalized Petersen graphs \(G(n,2)\) for \(n \geq 5\), and all non-isomorphic disconnecting sets that achieve the toughness are presented for \(5 \leq n \leq 15\). These results also provide an infinite class of \(G(n,2)\) for which the toughness equals \(\frac{5}{4}\), namely when \(n \equiv 0 (\mod 7)\).