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.

A family \(\mathcal{G}\) of connected graphs is said to be a family with constant metric dimension if \(\dim(G)\) does not depend upon the choice of \(G\) in \(\mathcal{G}\). In this paper, we study the metric dimension of some plane graphs obtained from convex polytopes by attaching a pendant edge to each vertex of the outer cycle in a plane representation of these convex polytopes. We prove that the metric dimension of these plane graphs is constant and only three vertices, appropriately chosen, suffice to resolve all vertices of these classes of graphs. It is natural to ask for the characterization of graphs \(G\) that are plane representations of convex polytopes having the property that \(\dim(G) = \dim(G’)\), where \(G’\) is obtained from \(G\) by attaching a pendant edge to each vertex of the outer cycle of \(G\).

It is well known that the properties about the power sequences of different classes of sign pattern matrices may be very different. In this paper, we consider the base of primitive nonpowerful zero-symmetric square sign pattern matrices without nonzero diagonal entry. The base set is shown to be \(\{2, 3, \ldots, 2n – 1\}\); the extremal sign pattern matrices with base \(2n – 1\) are characterized. As well, for the sign patterns with order \(3\), the sign patterns with bases \(3\), \(4\), \(5\) are characterized, respectively.

In this note, we study clique number, chromatic number,domination number and independence number of the intersection graph of subspaces of a finite dimensional vector space over a finite field.

A vertex-colored graph \(G\) is rainbow connected, if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex connection number of a connected graph \(G\), denoted \(\mathrm{rvc}(G)\), is the smallest number of colors that are needed in order to make \(G\) rainbow vertex connected. In this paper, we show that \(\mathrm{rvc}(G) \leq k\), if \(|E(G)| \geq \binom{n-k}{2} + k\), for \(k = 2, 3, n-4, n-5, n-6\). These bounds are sharp.

In order to find more sufficient conditions for the existence of hamiltonian cycles of graphs, Zhu, Li, and Deng proposed the definition of implicit degree of a vertex. In this paper, we consider the relationship between implicit degrees of vertices and the hamiltonicity of graphs, and obtain that: If the implicit degree sum for each pair of nonadjacent vertices of an induced claw or an induced modified claw in a \(2\)-connected graph \(G\) is more than or equal to \(|V(G)| – 1\), then \(G\) is hamiltonian with some exceptions. This extends a previous result of Cai et al. [J. Cai, H. Li and W. Ning, An implicit degree condition for hamiltonian cycles, Ars Combin. \(108 (2013) 365-378.]\) on the existence of hamiltonian cycles.

The general vertex-distinguishing total chromatic number of a graph \(G\) is the minimum integer \(k\), for which the vertices and edges of \(G\) are colored using \(k\) colors such that there are no two vertices possessing the same color-set, where a color-set of a vertex is a set of colors of the vertex and its incident edges. In this paper, we discuss the general vertex-distinguishing total chromatic number of complete bipartite graphs \(K_{m,n}\), and obtain the exact value of this number for some cases in terms of \(m\) and \(n\). Particularly, we give the bounds of this number for \(K_{n,n}\).

In this paper we characterize the unique graph whose algebraic connectivity is minimum among all connected graphs with given order and fixed matching number or edge covering number, and present two lower bounds for the algebraic connectivity in terms of the matching number or edge covering number.

Let \(G = (V, E)\) be a graph and \(\phi: V \cup E \to \{1, 2, \ldots, \alpha\}\) be a proper \(\alpha\)-total coloring of \(G\). Let \(f(v)\) denote the sum of the color on vertex \(v\) and the colors on the edges incident with \(v\). A neighbor sum distinguishing \(\alpha\)-total coloring of \(G\) is a proper \(\alpha\)-total coloring of \(G\) such that for each edge \(uv \in E(G)\), \(f(u) \neq f(v)\). Pileeniak and Woźniak first introduced this coloring and conjectured that such coloring exists for any simple graph \(G\) with maximum degree \(\Delta(G)\) if \(\alpha \geq \Delta(G) + 3\). The maximum average degree of \(G\) is the maximum of the average degree of its non-empty subgraphs, which is denoted by \(mad(G)\). In this paper, by using the Combinatorial Nullstellensatz and the discharging method, we prove that this conjecture holds for graphs with larger maximum average degree in their list versions. More precisely, we prove that if \(G\) is a graph with \(\Delta(G) \geq 11\) and \(mad(G) < 5\), then \(ch''_{\Sigma}(G) \leq \Delta(G) + 3\), where \(ch''_{\Sigma}(G)\) is the neighbor sum distinguishing total choosability of \(G\).

Let \(\mathcal{K}\) be a family of sets in \(\mathbb{R}^d\) and let \(k\) be a fixed natural number. Assume that every countable subfamily of \(K\) has an intersection expressible as a union of \(k\) starshaped sets, each having a \(d\)-dimensional kernel. Then \(S = \cap \{K : K \in \mathcal{K}\}\) is nonempty and is expressible as a union of \(k\) such starshaped sets.

If members of \(K\) are compact and every finite subfamily of \(\mathcal{K}\) has as its intersection a union of \(k\) starshaped sets, then \(S\) again is a union of \(k\) starshaped sets. An analogous result holds for unions of \(k\) convex sets. Finally, dual results hold for unions of subfamilies of \(\mathcal{K}\).