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.