The neighborhood or two-step graph, \(N(G)\), of a graph \(G\) is the intersection graph of the open neighborhoods of the vertices of \(G\), and \(L(G)\) is the line graph of \(G\). The class of graphs for which \(N[L(G)] \equiv L[N(G)]\) consists of those graphs for which every component is either \(K_1\), \(K_{1,3}\), or \(C_n\) where \(n \geq 3\) and \(n \neq 4\).

We consider several families of regular bipartite graphs, most of which are vertex-transitive, and investigate the problem of determining which ones are subgraphs of hypercubes. We define \(H_{k,r}\) as the graph on \(k\) vertices \(0,1,2,\ldots,k-1\) which form a \(k\)-cycle (when traversed in that order), with the additional edges \((i,i+r)\) for \(i\) even, where \(i+r\) is computed modulo \(k\). Since this graph contains both a \(k\)-cycle and an \((r+1)\)-cycle, it is bipartite (if and only if) \(k\) is even and \(r\) is odd. (For the “if” part, the bipartition \((X,Y)\) is given by \(X =\) even vertices and \(Y =\) odd vertices.) Thus we consider only the cases \(r = 3,5,7\). We find that \(H_{k,3}\) is a subgraph of a hypercube precisely when \(k \equiv 0 \pmod{4}\). \(H_{k,5}\) can be embedded in a hypercube precisely when \(k \equiv 0 \pmod{16}\). For \(r = 7\) we show that \(H_{k,7}\) is embeddable in a hypercube whenever \(k \equiv 0 \pmod{16}\).

A graph \(G\) is said to be embeddable in a set \(X\) if there exists a mapping \(f\) from \(E(G)\) to the set \(\mathcal{P}(X)\) of all subsets of \(X\) such that if we define a mapping \(g\) from \(V(G)\) to \(\mathcal{P}(X)\) by letting \(g(x)\) be the union of \(f(e)\) as \(e\) ranges over all edges incident with \(x\), then \(g\) is injective. We show that for each integer \(k \geq 2\), every graph of order at most \(2^k\) all of whose components have order at least \(3\) is embeddable in a set of cardinality \(k\).

Let \(D\) be a set of natural numbers. The distance graph \(G(D)\) has the integers as vertex set and two vertices \(u\) and \(v\) are adjacent if and only if \(|u – v| \in D\).
In the eighties, there have been some results concerning the chromatic number \(\chi(D)\) of these graphs, especially by Eggleton, Erdős, Skilton, and Walther. Most of these investigations are concentrated on distance graphs where the distance set \(D\) is a subset of primes.
This paper deals with the chromatic number of distance graphs of \(3\)-element distance sets without further restrictions for the elements of \(D\).

In this paper, we prove the existence of \(22\) new \(3\)-designs on \(26\) and \(28\) points. The base of the constructions are two designs with a small maximum size of the intersection of any two blocks.

A large set of KTS(\(v\)), denoted by LKTS(\(v\)), is a collection of (\(v-2\)) pairwise disjoint KTS(\(v\)) on the same set. In this article, some new LKTS(\(v\)) is constructed.

Let \(G\) be a graph with \(v\) vertices. If there exists a list of colors \(S_1, S_2, \ldots, S_v\) on its vertices, each of size \(k\), such that there exists a unique proper coloring for \(G\) from this list of colors, then \(G\) is called a uniquely \(k\)-list colorable graph. We prove that a connected graph is uniquely \(2\)-list colorable if and only if at least one of its blocks is not a cycle, a complete graph, or a complete bipartite graph. For each \(k\), a uniquely \(k\)-list colorable graph is introduced.

A supergraph \(H\) of a graph \(G\) is called tree-covered if \(H – E(G)\) consists of exactly \(|V(G)|\) vertex-disjoint trees, with each tree having exactly one point in common with \(G\). In this paper, we show that if a graph \(G\) can be packed in its complement and if \(H\) is a tree-covered supergraph of \(G\), then \(G\) itself is self-packing unless \(H\) happens to be a member of a specified class of graphs. This is a generalization of earlier results that almost all trees and unicyclic graphs can be packed in their complements.

Let \(T = (V,A)\) be an oriented graph with \(n\) vertices. \(T\) is completely strong path-connected if for each arc \((a,b) \in A\) and \(k\) (\(k = 2, \ldots, n-1\)), there is a path from \(b\) to \(a\) of length \(k\) (denoted by \(P_k(a,b)\)) and a path from \(a\) to \(b\) of length \(k\) (denoted by \(P’_k(a,b)\)) in \(T\). In this paper, we prove that a connected local tournament \(T\) is completely strong path-connected if and only if for each arc \((a,b) \in A\), there exist \(P_2(a,b)\) and \(P’ _2(a,b)\) in \(T\), and \(T\) is not of \(T_1 \ncong T_0\)-\(D’_8\)-type digraph and \(D_8\).

It was proved by Ellingham \((1984)\) that every permutation graph either contains a subdivision of the Petersen graph or is edge-\(3\)-colorable. This theorem is an important partial result of Tutte’s Edge-\(3\)-Coloring Conjecture and is also very useful in the study of the Cycle Double Cover Conjecture. The main result in this paper is that every permutation graph contains either a subdivision of the Petersen graph or two \(4\)-circuits and therefore provides an alternative proof of the theorem of Ellingham. A corollary of the main result in this paper is that every uniquely edge-\(3\)-colorable permutation graph of order at least eight must contain a subdivision of the Petersen graph.