Let \(G\) be a graph with \(r\) vertices of degree at least two. Let \(H\) be any graph. Consider \(r\) copies of \(H\). Then \(G \oplus H\) denotes the graph obtained by merging the chosen vertex of each copy of \(H\) with every vertex of degree at least two of \(G\). Let \(T_0\) and \(T^{A_1}\) be any two caterpillars. Define the first attachment tree \(T_1 = T_0 \oplus T^{A_1}\). For \(i \geq 2\), define recursively the \((i^{th})\) attachment tree \(T_i = T_{i-1} \oplus T^{A_i}\), where \(T_{i-1}\) is the \((i-1)^{th}\) attachment tree. Here one of the penultimate vertices of \(T^{A_1}\), \(i \geq 1\) is chosen for merging with the vertices of degree at least two of \(T_{i-1}\), for \(i \geq 1\). In this paper, we prove that for every \(i \geq 1\), the \(i\)th attachment tree \(T_i\) is graceful and admits a \(\beta\)-valuation. Thus it follows that the famous graceful tree conjecture is true for this infinite class of \((i^{th})\) attachment trees \(T’_is\), for all \(i \geq 1\). Due to the results of Rosa \([21]\) and El-Zanati et al. \([5]\) the complete graphs \(K_{2cm+1}\) and complete bipartite graphs \(K_{qm,pm}\), for \(c,p,m,q \geq 1\) can be decomposed into copies of \(i\)th attachment tree \(T_i\), for all \(i \geq 1\), where \(m\) is the size of such \(i\)th attachment tree \(T_i\).

A packing of \(K_n\) with copies of \(C_4\) (the cycle of length \(4\)), is an ordered triple \((V, \mathcal{C}, L)\), where \(V\) is the vertex set of the complete graph \(K_n\), \(C\) is a collection of edge-disjoint copies of \(C_4\), and \(L\) is the set of edges not belonging to a block of \(\mathcal{C}\). The number \(n\) is called the order of the packing and the set of unused edges \(L\) is called the leave. If \(C\) is as large as possible, then \((V, \mathcal{C}, L)\) is called a maximum packing MPC\((n, 4, 1)\). We say that an handcuffed design \(H(v, k, 1)\) \((W, P)\) is embedded into an MPC\((n, 4, 1)\) \((V, C, L)\) if \(W \subseteq V\) and there is an injective mapping \(f : \mathcal{P} \to \mathcal{C}\) such that \(P\) is a subgraph of \(f(P)\) for every \(P \in \mathcal{P}\). Let \(\mathcal{SH}(n, 4, k)\) denote the set of the integers \(v\) such that there exists an MPC\((n, 4, 1)\) which embeds an \(H(v, k, 1)\). If \(n \equiv 1 \pmod 8\) then an MPC\((n, 4, 1)\) coincides with a \(4\)-cycle system of order \(n\) and \(\mathcal{SH}(n, 4, k)\) is found by Milici and Quattrocchi, Discrete Math., \(174 (1997)\).

The aim of the present paper is to determine \(\mathcal{SH}(n, 4, k)\) for every integer \(n \not\equiv 1 \pmod 8\), \(n \geq 4\).

Given a sequence \(X = (x_1, x_2, \ldots, x_k)\), let \(Y = (y_1, y_2, \ldots, y_k)\) be a sequence obtained by rearranging the terms of \(X\). The total self-variation of \(Y\) relative to \(X\) is \(\zeta_X(Y) = \sum_{i=1}^k |y_i – x_i|\). On the other hand, let \(G = (V, E)\) be a connected graph and \(\phi\) be a permutation of \(V\). The total relative displacement of \(\phi\) is \(\delta_\phi(G) = \sum_{\{x \neq y\}\subset V} |d(x, y) – d(\phi(x), \phi(y))|\), where \(d(v, w)\) means the distance between \(v\) and \(w\) in \(G\). It’s clear that the total relative displacement of \(\phi\) is a total self-variation relative to the distance sequence of the graph.
In this paper, we determine the sequences which attain the maximum value of the total self-variation of all possible rearrangements \(Y\) relative to \(X\). Applying this result to the distance sequence of a graph, we find a best possible upper bound for the total relative displacement of a graph.

Let \(G\) be a simple undirected graph. Denote by \(mi(G)\) the number of maximal independent sets in \(G\). In this paper, we determine the second and third largest number of maximal independent sets in trees. Extremal trees achieving these values are also determined.

In \([5]\), the first author posed the problem of determining the spectrum of \((K_4, K_4 – e)\)-designs. In this article, we solve this problem, and also determine the spectrum of \((K_4, K_4 – e)\)-designs with exactly one \(K_4\) (or, equivalently, the spectrum of \((K_4 – e)\)-designs with a hole of size \(4\)). We also improve the bound for embedding a partial \(S(2,4,v)\) into a \((K_4, K_4 – e)\)-design given in \([5]\).

Given a digraph \(D\), its competition graph \(C(D)\) has the same vertex set as \(D\) and an edge between two vertices \(x\) and \(y\) if there is a vertex \(u\) so that \((x,u)\) and \((y,u)\) are arcs of \(D\). Motivated by a problem of communications, Kim and Roberts [2002] studied the competition graphs of the special digraphs known as semiorders and the graphs arising as competition graphs of acyclic digraphs satisfying conditions so called \(C(p)\) or \(C^*(p)\). While they could completely characterize the competition graph of an acyclic digraph satisfying \(C(p)\), they obtained only partial results on \(C^*(p)\) and left the general case open. In this paper, we answer their open question.

A graph \(G\) is said to be well-covered if every maximal independent set of \(G\) is of the same size. It has been shown that characterizing well-covered graphs is a co-NP-complete problem. In an effort to characterize some of these graphs, different subclasses of well-covered graphs have been studied. In this paper, we will introduce the subclass of stable well-covered graphs, which are well-covered graphs that remain well-covered with the addition of any edge. Some properties of stable well-covered graphs are given. In addition, the relationships between stable well-covered graphs and some other subclasses of well-covered graphs, including the surprising equivalence between stable well-covered graphs and other known subclasses, are proved.

Let \(G\) be a graph with vertex set \(V(G)\). For any \(S \subseteq V(G)\), we use \(w(G – S)\) to denote the number of components of \(G – S\). The toughness of \(G\), \(t(G)\), is defined as \(t(G) = \min\left\{\frac{|S|}{w(G – S)} \mid S \subseteq V(G), w(G – S) > 1\right\}\) if \(G\) is not complete; otherwise, set \(t(G) = +\infty\). In this paper, we consider the relationship between the toughness and the existence of fractional \((g, f)\)-factors. It is proved that a graph \(G\) has a fractional \((g, f)\)-factor if \(t(G) \geq \frac{b^2 – 1}{a}\).

An almost-bipartite graph is a non-bipartite graph with the property that the removal of a particular single edge renders the graph bipartite. A graph labeling of an almost-bipartite graph \(G\) with \(n\) edges that yields cyclic \(G\)-decompositions of the complete graph \(K_{2nt+1}\) (i.e., cyclic \((K_{2nt+1}, G)\)-designs) was recently introduced by Blinco, El-Zanati, and Vanden Eynden. They called such a labeling a \(\gamma\)-labeling. Here we show that the class of almost-bipartite graphs obtained from \(C_m\) by adding an edge joining distinct vertices in the same part in the bipartition of \(V(C_{2m})\) has a \(\gamma\)-labeling if and only if \(m \geq 3\). This, along with results of Blinco and of Froncek, shows that if \(G\) is a graph of size \(n\) consisting of a cycle with a chord, then there exists a cyclic \((K_{2nt+1},G)\)-design for every positive integer \(t\).

For a given graph \(H\), a graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) is said to be potentially \(H\)-graphic if there is a realization of \(\pi\) containing \(H\) as a subgraph. In this paper, we characterize potentially \(K_{1,1,6}\)-positive graphic sequences. This characterization implies the value of \(\sigma(K_{1,1,6}, n)\). Moreover, we also give a simple sufficient condition for a positive graphic sequence \(\pi = (d_1, d_2, \ldots, d_n)\) to be potentially \(K_{1,1,s}\)-graphic for \(n \geq s+2\) and \(s \geq 2\).