A pebbling step on a graph consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. We consider all weight functions defined on the vertices of a graph that satisfy some property \({P}\). The \({P}\)-pebbling number of a graph is the minimum number of pebbles needed in an arbitrary initial configuration so that, for any such weight function, there is a sequence of pebbling moves at the end of which each vertex has at least as many pebbles as required by the weight function. Some natural properties on graph products are induced by properties defined on the factor graphs. In this paper, we give a bound for the \({P}’\)-pebbling number associated with a particular kind of product property \({P}’\) in terms of the \({P}_i\)-pebbling numbers associated with the factor properties \({P}_1\) and \({P}_2\). We do this by introducing color pebbling, which may be of interest in its own right.

The \(k\)-th isoperimetric edge connectivity \(\gamma_k(G) = \min\{|[U,\overline{U}]| : U \subset V(G), |U| \geq k\}\). A graph \(G\) with \(\gamma_k(G) = \beta_k(G)\) is said to be \(\gamma_k\)-optimal, where \(\beta_k(G) = \min\{|[U,\overline{U}]| : U \subset V(G), |U| = k\}\). Let \(G\) be a connected \(d\)-regular graph. Write \(L(G)\) and \(P_2(G)\) the line graph and the 2-path graph of \(G\), respectively. In this paper, we derive some sufficient conditions for \(L(G)\) and \(P_2(G)\) to be \(\gamma_k\)-optimal.

In 1968, Vizing conjectured that for any edge chromatic critical graph \(G = (V,E)\) with maximum degree \(\Delta\) and independence number \(\alpha(G)\), \(\alpha(G) \leq \frac{|V|}{2}\). This conjecture is still open. In this paper, we prove that \(\alpha(G) \leq \frac{3\Delta-2}{5\Delta-2}|V|\) for \(\Delta = 11, 12\) and \(\alpha(G) \leq \frac{11\Delta-30}{17\Delta-30}|V|\) for \(13 \leq \Delta \leq 29\). This improves the known bounds for \(\Delta \in \{11, 12, \ldots, 29\}\).

Consider a communication network \(G\) in which a limited number of edge (arc) and/or vertex faults \(F\) might occur. A routing \(\rho\), i.e. a fixed path between each pair of vertices, for the network must be chosen without knowing which components might become faulty. The diameter of the surviving route graph \(R(G, \rho)/F\), where \(R(G, \rho)/F\) is a digraph with the same vertices as \(G – F\) and a vertex \(x\) being adjacent to another vertex \(y\) if and only if \(\rho(x, y)\) avoids \(F\), could be an important measurement for the routing \(\rho\). In this paper, the authors consider the Cartesian product digraphs whose factors satisfy some given conditions and show that the diameter of the surviving route graph is bounded by three for any minimal routing \(\rho\) when the number of faults is less than some integer. This result is also useful for the Cartesian product graphs and generalizes some known results.

The Tribonacci Zeta functions are defined by \(\zeta_T(s) = \sum_{k=1}^{\infty} {T_{k}^{-s}}\). We discuss the partial infinite sum \(\sum_{n=1}^{\infty} {T_{k}^{-s}}\) for some positive integer \(n\). We also consider the continued fraction expansion including Tribonacci numbers.

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with small graphs. In this paper we study \(\text{cr}(W_{1,m} \Box P_{n})\), the crossing number of Cartesian product \(W_{l,m} \Box P_{n}\), where \(W_{l,m}\) is the cone graph \(C_{m} + \overline{K_{l}}\). Klešč showed that \(\text{cr}(W_{1,3} \Box P_{n}) = 2n\) (Journal of Graph Theory, \(6(1994), 605-614)\)), \(\text{cr}(W_{1,4} \Box P_{n}) = 3n – 1\) and \(\text{cr}(W_{2,3} \Box P_{n}) = 4n\) (Discrete Mathematics, \(233(2001),353-359\)). Huang \(et\) \(al\). showed that \(\text{cr}(W_{1,m} \Box P_{n}) = (n – 1)\lfloor\frac{m}{2}\rfloor \lfloor\frac{m-1}{2}\rfloor +n+1\). for \(n \leq 3\) (Journal of Natural Science of Hunan Normal University,\(28(2005), 14-16)\). We extend these results and prove \(\text{cr}(W_{1,m} \Box P_{n}) = (n – 1) \left\lfloor \frac{m}{2} \right\rfloor\lfloor \frac{m-1}{2}\rfloor + n+1\) and \(\text{cr}(W_{2,m} \Box P_{n}) = 2n \left\lfloor \frac{m}{2} \right\rfloor\lfloor\frac{m-1}{2} \rfloor + 2n\).

A double-loop network (DLN) \(G(N;1,s)\) with \(1 < s < N\), is a digraph with the vertex set \(V = \{0,1,\ldots,N – 1\}\) and the edge set \(E=\{u\to v\mid v-u\equiv 1,s \pmod{N}, u,v \in V\}\). Let \(D(N;1,s)\) be the diameter of \(G\) and let us define \(D(N) = \min\{D(N;1,s)\mid 1 < s < N\}\) and \(lb(N) = \lceil\sqrt{3N}\rceil – 2\). A given DLN \(G(N;1,s)\) is called \(k\)-tight if \(D(N;1,s) = lb(N) + k\) (\(k \geq 0\)). A \(k\)-tight DLN is called optimal if \(D(N) = lb(N) + k\) (\(k \geq 0\)). It is known that finding \(k\)-tight optimal DLN is a difficult task as the value \(k\) increases. In this work, a practical algorithm is derived for finding \(k\)-tight optimal double-loop networks (\(k \geq 0\)), and it is proved that the average complexity to judge whether there exists a \(k\)-tight \(L\)-shaped tile with \(N\) nodes is \(O(k^2)\). As application examples, we give some \(9\)-tight optimal DLN and their infinite families.

Let \(k\) be a positive integer and let \(G = (V(G), E(G))\) be a graph with \(|V(G)| \geq 4k\). In this paper, it is proved that if the minimum degree sum is at least \(6k – 1\) for each pair of nonadjacent vertices in \(V(G)\), then \(G\) contains \(k\) vertex-disjoint chorded cycles. This result generalizes the main Theorem of Finkel. Moreover, the degree condition is sharp in general.

Let \(G = (V, E)\) be a finite simple connected graph. For any vertex \(v\) in \(V\), let \(N_G(v) = \{u \in V: uv \in E\}\) be the open neighbourhood of \(v\), and let \(N_G[v] = N_G(v) \cup \{v\}\) be the closed neighbourhood of \(v\). A connected graph \(G\) is said to be neighbourhood highly irregular (or simply NHI) if for any vertex \(v \in V\), any two distinct vertices in the open neighbourhood of \(v\) have distinct closed neighbourhood sets. In this paper, we give a necessary and sufficient condition for a graph to be NHI. For any \(n \geq 1\), we obtain a lower bound for the order of regular NHI graphs and a sharp lower bound for the order of NHI graphs with clique number \(n\), which is better than the bound attained earlier.

In this paper, we initiate the study of \(k\)-connected restrained domination in graphs. Let \(G = (V,E)\) be a graph. A \(k\)-connected restrained dominating set is a set \(S \subseteq V\) where \(S\) is a restrained dominating set and \(G[S]\) has at most \(k\) components. The \(k\)-connected restrained domination number of \(G\), denoted by \(\gamma_r^k(G)\), is the smallest cardinality of a \(k\)-connected restrained dominating set of \(G\). First, some exact values and sharp bounds for \(\gamma_r^k(G)\) are given in Section 2. Then, the necessary and sufficient conditions for \(\gamma_r(G) = \gamma_r^1(G) = \gamma_r^2(G)\) are given if \(G\) is a tree or a unicyclic graph in Section 3 and Section 4.