A cycle \(C\) in a graph \(G\) is said to be dominating if \(E(G-C) = 0\). Enomoto et al. showed that if \(G\) is a 2-connected triangle-free graph with \(\alpha(G) \leq 2\kappa(G) – 2\), then every longest cycle is dominating. But it is unknown whether the condition on the independence number is sharp. In this paper, we show that if \(G\) is a 2-connected triangle-free graph with \(\alpha(G) \leq 2\kappa(G) – 1\), then \(G\) has a longest cycle which is dominating. This condition is best possible.

In this paper, we obtain the explicit recurrences of the independence polynomials of polygonal cactus chains of two classes, and show that they are the extremal polygonal cactus chains with respect to the number of independent sets.

We prove that the power of cycles \(C_n^2\) for odd \(n\) are antimagic. We provide explicit constructions to demonstrate that all powers of cycles \(C_n^2\) for odd \(n\) are antimagic and their vertex sums form a set of successive integers.

A graph \(G = (V, E)\) is Skolem-graceful if its vertices can be labelled \(1, 2, \ldots, |V|\), so that the edges are labelled \(1, 2, \ldots, |E|\), where each edge label is the absolute difference of the labels of the two end-vertices. It is shown that a \(k\)-star is Skolem-graceful only if at least one star has even size or \(k \equiv 0\) or \(1 \pmod{4}\), and for \(k \leq 5\), a \(k\)-star is Skolem-graceful if at least one star has even size or \(k \equiv 0\) or \(1 \pmod{4}\). In this paper, we show that \(k\)-stars are Skolem-graceful if at least one star has even size or \(k \equiv 0\) or \(1 \pmod{4}\) for all positive integer \(k\).

Let \(\Gamma\) be a \(d\)-bounded distance-regular graph with diameter \(d \geq 3\) and with geometric parameters \((d, b, \alpha)\). Pick \(x \in V(\Gamma)\), and let \(P(x)\) be the set of all subspaces containing \(x\). Suppose \(P(x, m)\) is the set of all subspaces in \(P(x)\) with diameter \(m\), where \(1 \leq m < d\). Define a graph \(\Gamma'\) whose vertex-set is \(P(x, m)\), and in which \(\Delta_1\) is adjacent to \(\Delta_2\) if and only if \(d(\Delta_1 \cap \Delta_2) = m – 1\). We prove that \(\Gamma'\) is a distance-regular graph and compute its intersection numbers.

Let \(G\) be a \(contraction-critical\) \(\kappa\)-connected graph. It is known (see Graphs and Combinatorics, \(7 (1991) 15-21\)) that the minimum degree of \(G\) is at most \(\lfloor \frac{5\kappa}{4} \rfloor – 1\). In this paper, we show that if \(G\) has at most one vertex of degree \(\kappa\), then either \(G\) has a pair of adjacent vertices such that each of them has degree at most \(\lfloor \frac{5\kappa}{4} \rfloor – 1\), or there is a vertex of degree \(\kappa\) whose neighborhood has a vertex of degree at most \(\lfloor \frac{4\kappa}{4} \rfloor – 1\). Moreover, if the minimum degree of \(G\) equals to \(\frac{5\kappa}{4} – 1\) (and thus \(\kappa = 0 \mod 4\)), Su showed that \(G\) has \(\kappa\) vertices of degree \(\frac{5\kappa}{4} – 1\), guessed that \(G\) has \(\frac{3\kappa}{2}\) such vertices (see Combinatorics Graph Theory Algorithms and Application (Yousef Alavi et. al Eds.),World Scientific, \(1993, 329-337\)). Here, we verify that this is true.

A simple Kirkman packing design \(SKPD(\{w, w+1\}, v)\) with index \(\lambda\) is a resolvable packing with distinct blocks and maximum possible number of parallel classes, each containing \(u =v-w \lfloor \frac{v}{w} \rfloor\) blocks of size \(w+1\) and \(\frac{v-u(w+1)}{w}\) blocks of size \(w\), such that each pair of distinct elements occurs in at most \(\lambda\) blocks. In this paper, we solve the spectrum of simple Kirkman packing designs \(SKPD(\{3, 4\}, v)\) with index \(2\) completely.

In this paper, we study the matrices related to the idempotent number and the number of planted forests with \(k\) components on the vertex set \([n]\). As a result, the factorizations of these two matrices are obtained. Furthermore, the discussion goes to the generalized case. Some identities and recurrences involving these two special sequences are also derived from the corresponding matrix representations.

A Roman dominating function on a graph \(G = (V, E)\) is a function \(f : V \rightarrow \{0, 1, 2\}\) satisfying the condition that every vertex \(u\) for which \(f(u) = 0\) is adjacent to at least one vertex \(v\) for which \(f(v) = 2\). The weight of a Roman dominating function is the value \(f(V) = \sum_{u \in V} f(u)\). The minimum weight of a Roman dominating function on a graph \(G\), denoted by \(\gamma_R(G)\), is called the Roman domination number of \(G\). In [E.J. Cockayne, P.A. Dreyer, Jr.,S.M. Hedetniemi, S.T. Hedetniemi, Roman domination in graphs,Discrete Math. \(278(2004) 11-22.]\), the authors stated a proposition which characterized trees which satisfy \(\gamma_R(T) = \gamma(T) + 2\), where \(\gamma(T)\) is the domination number of \(T\). The authors thought the proof of the proposition was rather technical and chose to omit its proof; however, the proposition is actually incorrect. In this paper, we will give a counterexample of this proposition and introduce the correct characterization of a tree \(T\) with \(\gamma_R(T) = \gamma(T) + 2\).

Let \(G\) be a graph on \(2n\) vertices with minimum degree \(r\). We show that there exists a two-coloring of the vertices of \(G\) with colors \(-1\) and \(+1\), such that all open neighborhoods contain more \(+1\)’s than \(-1\)’s, and altogether the number of \(+1\)’s does not exceed the number of \(-1\)’s by more than \(O(\frac{n}{\sqrt{n}})\).