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}\) 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 a path with at least \(3\) edges by adding an edge joining distinct vertices of the path an even distance apart has a \(\gamma\)-labeling.

The locally twisted cube \(LTQ_n\) is an important variation of hypercube and possesses many desirable properties for interconnection networks. In this paper, we investigate the problem of embedding paths in faulty locally twisted cubes. We prove that a path of length \(l\) can be embedded between any two distinct vertices in \(LTQ_n – F\) for any faulty set \(F \subseteq V(LTQ_n) \cup E(LTQ_n)\) with \(|F| \leq n-3\) and any integer \(l\) with \(2^{n-1} \leq l \leq |V(LTQ_n – F)| – 1\) for any integer \(n > 3\). The result is tight with respect to the two bounds on path length \(l\) and faulty set size \(|F|\) for a successful embedding.

A \(G\)-design is a partition of \(E(K_v)\) in which each element induces a copy of \(G\). The existence of \(G\)-designs with the additional property that they contain no proper subsystems has been previously settled when \(G \in \{K_3, K_4 – e\}\). In this paper, the existence of \(P_m\)-designs which contain no proper subsystems is completely settled for every value of \(m\) and \(v\).

The Randić index of an organic molecule whose molecular graph is \(G\) is the sum of the weights \((d(u)d(v))^{-\frac{1}{2}}\) of all edges \(uv\) of \(G\), where \(d(u)\) and \(d(v)\) are the degrees of the vertices \(u\) and \(v\) in \(G\). In this paper, we give a sharp lower bound on the Randić index of cacti with perfect matchings.

Let \(\text{ASG}(2v+1,v;\mathbb{F}_q)\) be the \((2v+1)\)-dimensional affine-singular symplectic space over the finite field \(\mathbb{F}_q\) and let \(\text{ASp}_{2v+1}(\mathbb{F}_q)\) be the affine-singular symplectic group of degree \(2v+1\) over \(\mathcal{F}_q\). For any orbit \(O\) of flats under \(\text{ASp}_{2v+1}(\mathbb{F}_q)\), let \(\mathcal{L}\) be the set of all flats which are intersections of flats in \(O\) such that \(O \subseteq \mathcal{L}\) and assume the intersection of the empty set of flats in \(\text{ASG}(2v+1,v;\mathbb{F}_q)\) is \(\mathbb{F}_q^{2v+1}\). By ordering \(\mathcal{L}\) by ordinary or reverse inclusion, two lattices are obtained. This article discusses the relations between different lattices, classifies their geometricity, and computes their characteristic polynomial.

Let \(\gamma_c(G)\) be the connected domination number of \(G\).A graph is \(k\)-\(\gamma_c\)-critical if \(\gamma_c(G) = k\) and \(\gamma_c(G + uv) < \gamma_c(G)\) for any nonadjacent pair of vertices \(u\) and \(v\) in the graph \(G\). In this paper, we show that the diameter of a \(k\)-\(\gamma_c\)-critical graph is at most \(k\) and this upper bound is sharp.

A \(b\)-coloring of a graph \(G\) by \(k\) colors is a proper \(k\)-coloring of the vertices of \(G\) such that in each color class there exists a vertex having neighbors in all the other \(k-1\) color classes. The \(b\)-chromatic number \(\varphi(G)\) of a graph \(G\) is the maximum \(k\) for which \(G\) has a \(b\)-coloring by \(k\) colors. This concept was introduced by R.W. Irving and D.F. Manlove in \(1999\). In this paper, we study the \(b\)-chromatic numbers of the cartesian products of paths and cycles with complete graphs and the cartesian product of two complete graphs.