A subset \(S \subseteq V(G)\) is an independent dominating set for \(G\) if \(S\) is independent and each vertex of \(G\) is either in \(S\) or adjacent to some vertex of \(S\). Let \(i(G)\) denote the minimum cardinality of an independent dominating set for \(G\). For a positive integer \(t\), a graph \(G\) is \(t\)-i-critical if \(i(G) = t\), but \(i(G + uv) < t\) for any pair of non-adjacent vertices \(u\) and \(v\) of \(G\). Further, for a positive integer \(k\), a graph \(G\) is \(k\)-factor-critical if for every \(S \subseteq V(G)\) with \(|S| = k\), \(G – S\) has a perfect matching. In this paper, we provide sufficient conditions for connected \(3\)-i-critical graphs to be \(k\)-factor-critical in terms of connectivity and minimum degree.

Let \(G = (V, E)\) be a simple graph, \(I(G)\) its incidence matrix. The incidence energy of \(G\), denoted by \(IE(G)\), is the sum of the singular values of \(I(G)\). The incidence energy \(IE(G)\) of a graph is a recently proposed quantity. However, \(IE(G)\) is closely related with the eigenvalues of the Laplacian and signless Laplacian matrices of \(G\). The trees with the maximal, the second maximal, the third maximal, the smallest, the second smallest, and the third smallest incidence energy were characterized. In this paper, the trees with the fourth and fifth smallest incidence energy are characterized by the quasi-order method and Coulson integral formula, respectively. In addition, the fourth maximal incidence energy among all trees on \(n\) vertices is characterized.

A Roman dominating function (or simply RDF) on a graph \(G = (V(G), E(G))\) is a labeling \(f: V(G) \to \{0, 1, 2\}\) satisfying the condition that every vertex with label \(0\) has at least a neighbor with label \(2\). The Roman domination number, \(\gamma_R(G)\), of \(G\) is the minimum of \(\sum_{v \in V(G)} f(v)\) over such functions. The Roman bondage number, \(b_R(G)\), of a graph \(G\) with maximum degree at least two is the minimum cardinality among all sets \(E \subseteq E(G)\) for which \(\gamma_R(G – E) > \gamma_R(G)\). It was conjectured that if \(G\) is a graph of order \(n\) with maximum degree at least two, then \(b_R(G) \leq n – 1\). In this paper, we settle this conjecture. More precisely, we prove that for every connected graph of order \(n \geq 3\), \(b_R(G) \leq \min\{n – 1, n – \gamma_R(G) + 5\}\).

Let \(G\) be a finite and simple graph with vertex set \(V(G)\), and let \(f: V(G) \to \{-1, 1\}\) be a two-valued function. If \(k \geq 1\) is an integer and \(\sum_{x\in N[v]}f(x) \geq k\) for each \(v \in V(G)\), where \(N[v]\) is the closed neighborhood of \(v$, then \(f\) is a signed \(k\)-dominating function on \(G\). A set \(\{f_1, f_2, \ldots, f_d\}\) of distinct signed \(k\)-dominating functions on \(G\) with the property that \(\sum_{i=1}{d}f_i(v) \leq j\) for each \(x \in V(G)\), is called a signed \((j, k)\)-dominating family (of functions) on \(G\), where \(j \geq 1\) is an integer. The maximum number of functions in a signed \((j, k)\)-dominating family on \(G\) is the signed \((j, k)\)-domatic number on \(G\), denoted by \(d_{jkS}(G)\).

The aim of this paper is to classify the vertex-primitive symmetric graphs of order \(6p\). These works were essentially done in \([1]\). But in \([1]\) there is no such situation: \(G = \mathrm{PSL}(2, 13)\) acting on the set of cosets of subgroup \(H \cong D_{14}\). Then \(m = |\Omega| = 78 = 6p\), \(G\) has rank \(9\), and the sub-orbits of \(G\) have one of length \(1\), five of length \(7\), and three of length \(14\). In this paper, we give a complete list of symmetric graphs of order \(6p\).

Let \(p\) be an odd prime and \(n\) be a positive integer. For any positive integer \(d \leq n\), let \(g_1(x) = 1 + x^{p^{n-d}} + x^{{2p}^{n-d}} + \ldots + x^{(p-1)p^{n-d}}\) and \(g_2(x) = 1 + x^{p^{n-d+1}} + x^{2p^{n-d+1}} + \ldots + x^{{(p^{d-1}-1)}{p^{n-d+1}}}\). In this paper, we provide a method to determine the weight distributions of binary cyclic codes of length \(p^n\) generated by the polynomials \(g_1(x)\) and \(g_01(x)g_2(x)\), which is effective for small values of \(p\) and \(d\).

A spanning tree with no vertices of degree two of a graph is called a homeomorphically irreducible spanning tree (or HIST) of the graph. It has been proved that every planar triangulation \(G\) with at least four vertices has a HIST \(H\) [1]. However, the previous result asserts nothing whether the degree of a fixed vertex \(v\) of \(G\) is at least three or not in \(H\). In this paper, we prove that if a planar triangulation \(G\) has \(2n\) (\(n \geq 2\)) vertices, then, for any vertex \(v\), \(G\) has a HIST \(H\) such that the degree of \(v\) is at least three in \(H\). We call such a spanning tree a rooted HIST of \(G\) with root \(v\).

A graph \(G\) is Hamiltonian connected, if there is a Hamiltonian path between every two distinct vertices of \(G\). A Hamiltonian connected graph \(G\) is called critical Hamiltonian connected (CHC), if for every edge \(e\) in \(G\), the graph \(G – e\) is not Hamiltonian connected. In this paper, we study the properties of CHC graphs.

A generalized \(\theta\)-graph is composed of at least three internal disjoint paths (at most one of them is with length 1) which have the same initial vertex and the same terminal vertex. If the initial vertex and the terminal vertex are the same in a generalized \(\theta\)-graph, then the generalized \(\theta\)-graph is called a degenerated \(\theta\)-graph or a petal graph. In this paper, two graft transformations that increase or decrease the \(Q\)-spectral radius of a graph are represented. With them, for the generalized \(\theta\)-graphs and petal graphs with order \(n\), the extremal graphs with the maximal \(Q\)-spectral radius and the extremal graphs with the minimal \(Q\)-spectral radius are characterized, respectively.