Let \(G = (X, Y, E(G))\) be a bipartite graph with vertex set \(V(G) = X ! Y\) and edge set \(E(G)\), and let \(g, f\) be two nonnegative integer-valued functions defined on \(V(G)\) such that \(g(x) \leq f(x)\) for each \(x \in V(G)\). A \((g, f)\)-factor of \(G\) is a spanning subgraph \(F\) of \(G\) such that \(g(x) \leq d_F(x) \leq f(x)\) for each \(x \in V(F)\); a \((g, f)\)-factorization of \(G\) is a partition of \(E(G)\) into edge-disjoint \((g, f)\)-factors. Let \(\mathcal{F} = \{F_1, F_2, \ldots, F_m\}\) be a factorization of \(G\) and \(H\) be a subgraph of \(G\) with \(m\) edges. If \(F_i\), \(1 \leq i \leq m\), has exactly \(r\) edges in common with \(H\), we say that \(F_i\) is \(r\)-orthogonal to \(H\). In this paper, it is proved that every bipartite \((0, mf-(m-1)r)\)-graph has \((0, f)\)-factorizations randomly \(r\)-orthogonal to any given subgraph with \(m\) edges if \(2r \leq f(x)\) for any \(x \in V(G)\).

We define an \(r\)-capacitated dominating set of a graph \(G = (V,E)\) as a set \(\{v_1, \ldots, v_k\} \subseteq V\) such that there is a partition \((V_1, \ldots, V_k)\) of \(V\) where for all \(i\), \( v_i \in V_i\), \(v_i\) is adjacent to all of \(V_i – \{v_i\}\), and \(|V_i| \leq r + 1\). \(\daleth_r(G)\) is the minimum cardinality of an \(r\)-capacitated dominating set. We show properties of \(\daleth_r\), especially as regards the trivial lower bound \(|V|/(r + 1)\). We calculate the value of the parameter in several graph families, and show that it is related to codes and polyominoes. The parameter is \(NP\)-complete in general to compute, but a greedy approach provides a linear-time algorithm for trees.

On the basis of joint trees introduced by Yanpei Liu, by choosing different spanning trees and classifying the associated surfaces, we obtain the explicit expressions of genus polynomials for three types of graphs, namely \(K_5^n, W_6^n\) and \(K_{3,3}^n\), which are different from the graphs whose embedding distributions by genus have been obtained. And \(K_5^n\) and \(K_{3,3}^n\) are non-planar.

We develop the necessary machinery in order to prove that hexagonal tilings are uniquely determined by their Tutte polynomial, showing as an example how to apply this technique to the toroidal hexagonal tiling.

A \((d,1)\)-totel labelling of a graph \(G\) is an assignment of integers to \(V(G) \cap E(G)\) such that: (i) any two adjacent vertices of \(G\) receive distinct integers, (ii) any two adjacent edges of \(G\) receive distinct integers, and (iii) a vertex and its incident edge receive integers that differ by at least \(d\) in absolute value. The span of a \((d,1)\)-total labelling is the maximum difference between two labels. The minimum span of labels required for such a \((d, 1)\)-total labelling of \(G\) is called the \((d, 1)\)-total number and is denoted by \(\lambda_d^T(G)\). In this paper, we prove that \(\lambda_d^T(G)\geq d+r+1 \) for \(r\)-regular nonbipartite graphs with \(d \geq r \geq 3\) and determine the \((d, 1)\)-total numbers of flower snarks and of quasi flower snarks.

Let \(G = (V,E)\) be a simple graph with the vertex set \(V\) and the edge set \(E\). \(G\) is a sum graph if there exists a labelling \(f\) of the vertices of \(G\) into distinct positive integers such that \(uv \in E\) if and only if \( f(w)=f(u) + f(v) \) for some vertex \(w \in V\). Such a labelling \(f\) is called a sum labelling of \(G\). The sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices which result in a sum graph when added to \(G\). Similarly, the integral sum graph and the integral sum number \(\zeta(G)\) are also defined. The difference is that the labels may be any distinct integers.
In this paper, we will determine that
\[\begin{cases}
0 = \zeta(\overline{P_4}) < \sigma(\overline{P_4}) = 1;\\ 1 = \zeta(\overline{P_5}) < \sigma(\overline{P_5}) = 2;\\ 3 = \zeta(\overline{P_6}) < \sigma(\overline{P_6}) = 4;\\ \zeta(\overline{P_n}) = \sigma(\overline{P_n}) = 0, \text{ for } n = 1, 2, 3;\\ \zeta(\overline{P_n}) = \sigma(\overline{P_n}) = 2n – 7, \text{ for } n \geq 7; \end{cases}\] and \[\begin{cases} 0 = \zeta(\overline{F_5}) < \sigma(\overline{F_5}) = 1;\\ 2 = \zeta(\overline{F_5}) < \sigma(\overline{F_6}) = 2;\\ \zeta(\overline{F_c}) = \sigma(\overline{F_n}) = 0, \text{ for } n =3,4;\\ \zeta(\overline{F_n}) = \sigma(\overline{F_n}) = 2n – 8, \text{ for } n \geq 7. \end{cases}\]

The Padmakar-Ivan (PI) index is a Wiener-Szeged-like topological index which reflects certain structural features of organic molecules. In this paper, we study the PI indices of bicyclic graphs whose cycles do not share two or more common vertices.