A graph-pair of order \(t\) is two non-isomorphic graphs \(G\) and \(H\) on \(t\) non-isolated vertices for which \(G \cup H \cong K_t\) for some integer \(t \geq 4\). Given a graph-pair \((G, H)\), we say \((G, H)\) divides some graph \(K\) if the edges of \(K\) can be partitioned into copies of \(G\) and \(H\) with at least one copy of \(G\) and at least one copy of \(H\). We will refer to this partition as a \((G, H)\)-multidecomposition of \(K\).

Let \(V\) denote the \(n\)-dimensional row vector space over a finite field \(\mathbb{F}_q\), and let \(W\) be a subspace of dimension \(n-d\). Let \(L(n,d) = \mathcal{P} \cup \{0\}\), where \({P} = \{A | A \text{ is a subspace of } V, A + W = V\}\). Partially ordered by ordinary or reverse inclusion, two families of finite atomic lattices are obtained. This article discusses their geometricity, and computes their characteristic polynomials.

A graph \(G\) is called \(H\)-equipackable if every maximal \(H\)-packing in \(G\) is also a maximum \(H\)-packing in \(G\). All \(M_2\)-equipackable graphs and \(P_3\)-equipackable graphs have been characterized. In this paper, \(P_k\)-equipackable paths, \(P_k\)-equipackable cycles, \(M_3\)-equipackable paths and \(M_3\)-equipackable cycles are characterized.

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.