Let \(P_{k+1}\) denote a path of length \(k\) and let \(C_k\) denote a cycle of length \(k\). A triangle is a cycle of length three. As usual, \(K_n\) denotes the complete graph on \(n\) vertices. It is shown that for all nonnegative integers \(p\) and \(q\) and for all positive integers \(n\), \(K_n\) can be decomposed into \(p\) copies of \(P_4\) and \(q\) copies of \(C_3\) if and only if \(3(p+q) = e(K_n)\), \(p \neq 1\) if \(n\) is odd, and \(p \geq \frac{n}{2}\) if \(n\) is even.

Motivated by Kotzig and Rosa’s concept of edge magic deficiency, Figueroa-Centeno, Ichishima, and Muntaner-Batle defined a similar concept for super edge magic total labelings. The super edge magic deficiency of a graph \(G\), which is denoted by \(\mu_s(G)\), is the minimum nonnegative integer \(n\) \(+\infty\) if there exists no such \(n\). In this paper, we study the super edge magic deficiency of kite graphs.

The corona of two graphs \(G\) and \(H\), written as \(G \odot H\), is the graph obtained by taking one copy of \(G\) and \(|V(G)|\) copies of \(H\), and then joining the \(i\)th vertex of \(G\) to every vertex in the \(i\)th copy of \(H\). In this paper, we present the explicit formulae for the Wiener, hyper-Wiener and reverse-Wiener indices of the corona of two graphs.

The energy of a graph \(G\), denoted by \(E(G)\), is defined to be the sum of absolute values of all eigenvalues of the adjacency matrix of \(G\). Let \(\mathcal{B}(p, q)\) denote the set of bipartite unicyclic graphs with a \((p, q)\)-bipartition, where \(q \geq p \geq 2\). Recently, Li and Zhou [MATCH Commun. Math. Comput. Chem. \(54 (2005) 379-388]\) conjectured that for \(q \geq 3\), \(E(B(3, q)) > E(H(3, q))\), where \(B(3, q)\) and \(H(3, q)\) are respectively graphs as shown in Fig. 1. In this note, we show that this conjecture is true for \(3 \leq q \leq 217\). As a byproduct, we determined the graph with minimal energy among all graphs in \(\mathcal{B}(3, q)\).

In this work, infinite similarities of permutation groups are investigated by means of new methods. For this purpose, we handle distinct groups on the set of natural numbers and we give the separation of the subgroups of them. Afterwards, we give the matrix representation of this groups.

This paper studies edge- and total-colorings of graphs in which (all or only adjacent) vertices are distinguished by their sets of colors. We provide bounds for the minimum number of colors needed for such colorings for the Cartesian product of graphs along with exact results for generalized hypercubes. We also present general bounds for the direct, strong and lexicographic products.

The pebbling number \(f(G)\) of a graph \(G\) is the smallest number \(k\) such that, however \(n\) pebbles are placed on the vertices of \(G\), we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs \(G\) and \(H\), \(f(G \times H) \leq f(G)f(H)\), where \(G \times H\) represents the Cartesian product of \(G\) and \(H\). In this paper, we prove that \(f(G \times H) \leq f(G)f(H)\) when \(G\) has the two-pebbling property and \(H = K_{r,s}^{ – k}\), a graph obtained from the \(r \times s\) complete bipartite graph \(K_{r,s}\) by deleting \(k\) edges which form a matching. We also show that Graham’s conjecture holds for \(K_{r,s}^{-k_1} \times K_{m,n}^{-k_2}\).

The Hosoya polynomial of a graph \(G\) is defined as \(H(G,x) = \sum\limits_{k\geq 0} d(G,k)x^k,\)
where \(d(G, k)\) is the number of vertex pairs at distance \(k\) in \(G\). The calculation of Hosoya polynomials of molecular graphs is a significant topic because some important molecular topological indices such as Wiener index, hyper-Wiener index, and Wiener vector, can be obtained from Hosoya polynomials. Hosoya polynomials of zig-zag open-ended nanotubes have been given by Xu and Zheng et al. A capped zig-zag nanotube \(T(p, q)[C, D; a]\) consists of a zig-zag open-ended nanotube \(T(p, q)\) and two caps \(C\) and \(D\) with the relative position \(a\) between \(C\) and \(D\). In this paper, we give a general formula for calculating the Hosoya polynomial of any capped zig-zag nanotube. By the formula, the Hosoya polynomial of any capped zig-zag nanotube can be deduced. Furthermore, it is also shown that any two non-isomorphic capped zig-zag nanotubes \(T(p, q)[C, D; a_1]\), \(T(p, q’)[C, D; a_2]\) with \(q’ \geq q^* \geq p+1\) have the same Hosoya polynomial, where \(q^*\) is an integer that depends on the structures of \(C\) and \(D\).

Ewa Wojcicka (Journal of Graph Theory, \(14(1990), 205-215)\) showed that every connected, 3-color-critical graph on more than 6 vertices has a Hamiltonian path. Henning et al. (Discrete Mathematics, \(161(1996), 175-184)\) defined a graph \(G\) to be \(k\)-\((\gamma, d)\)-critical graph if \(\gamma(G) = k\) and \(\gamma(G + uv) = k – 1\) for each pair \(u, v\) of nonadjacent vertices of \(G\) that are at distance at most \(d\) apart. They asked if a 3-\((\gamma, 2)\)-critical graph must contain a dominating path. In this paper, we show that every connected, 3-\((\gamma, 2)\)-critical graph must contain a dominating path. Further, we show that every connected, 3-\((\gamma, 2)\)-critical graph on more than 6 vertices has a Hamiltonian path.

Let \(d(u,v)\) denote the distance between two distinct vertices of a connected graph \(G\) and \(diam(G)\) be the diameter of \(G\). A radio labeling \(f\) of \(G\) is an assignment of positive integers to the vertices of \(G\) satisfying \(d(u,v) + |f(u) – f(v)| \geq diam(G) + 1\). The maximum integer in the range of the labeling is its span. The radio number of \(G\), denoted by \(rn(G)\), is the minimum possible span. In \([7]\) M. Farooq et al. found the lower bound for the radio number of generalized gear graph. In this paper, we give an upper bound for the radio number of generalized gear graph, which coincides with the lower bound found in \([7]\).