In \([2]\) Stefano Innamorati and Mauro Zannetti gave a characterization of the planes secant to a non-singular quadric in \({P}G(4, q)\). Their result is based on a particular hypothesis (which we call “polynomial”) that, as the same authors wrote at the end of the paper, could not exclude possible sporadic cases. In this paper, we improve their result by giving a characterization without the “polynomial” hypothesis. So, possible sporadic cases are definitely excluded.

This paper generalizes the results of Guiduli [B. Guiduli, On incidence coloring and star arboricity of graphs. Discrete Math. \(163
(1997), 275-278]\) on the incidence coloring of graphs to the fractional incidence coloring. Tight asymptotic bounds analogous to Guiduli’s results are given for the fractional incidence chromatic number of graphs. The fractional incidence chromatic number of circulant graphs is studied. Relationships between the \(k\)-tuple incidence chromatic number and the incidence chromatic number of the direct products and lexicographic products of graphs are established. Finally, for planar graphs \(G\), it is shown that if \(\Delta(G) \neq 6\), then \(\chi_i(G) \leq \Delta(G) + 5\); if \(\Delta(G) = 6\), then \(\chi_i(G) \leq \Delta(G) + 6\); where \(\chi_i(G)\) denotes the incidence chromatic number of \(G\). This improves the bound \(\chi_i(G) \leq \Delta(G) + 7\) for planar graphs given in [M. Hosseini Dolama, E. Sopena, X. Zhu, Incidence coloring of k-degenerated graphs, Discrete Math. \(283 (2004)\), no. \(1-3, 121-128]\).

Let \(P(G, \lambda)\) be the chromatic polynomial of a graph \(G\). A graph \(G\) is chromatically unique if for any graph \(H\), \(P(H, \lambda) = P(G, \lambda)\) implies \(H \cong G\). Some sufficient conditions guaranteeing that certain complete tripartite graph \(K(l, n, r)\) is chromatically unique were obtained by many scholars. Especially, in 2003, H.W. Zou showed that if \(n > \frac{1}{3}(m^2+k^2+mk+2\sqrt{m^2 + k^2 + mk} + m – k)\), where \(n, k\), and \(m\) are non-negative integers, then \(K(n – m, n, n + k)\) is chromatically unique (or simply \(\lambda\)-unique). In this paper, we show that for any positive integers \(n, m\), and \(k\), let \(G = K(n – m, n, n + k)\), where \(m \geq 2\) and \(k \geq 1\), if \(n \geq \max\{\lceil \frac{1}{4}m^2 + m + k \rceil, \lceil \frac{1}{4}m^2 + \frac{3}{2}m + 2k – \frac{11}{4} \rceil, \lceil mk + m – k + 1 \rceil\}\), then \(G\) is \(\chi\)-unique. This improves upon H.W. Zou’s result in the case \(m \geq 2\) and \(k \geq 1\).

In this paper, it is proved that a toroidal graph without cycles of length \(k\) for each \(k \in \{4, 5, 7, 10\}\) is \(3\)-choosable.

In this paper, we investigate the transitive Cayley graphs of strong semilattices of rectangular groups, and of normal bands, respectively. We show under which conditions they enjoy the property of automorphism vertex transitivity in analogy to Cayley graphs of groups.

A family of connected graphs \(\mathcal{G}\) is said to be a family with constant metric dimension if its metric dimension is finite and does not depend upon the choice of \(G\) in \(\mathcal{G}\). In this paper, we study the metric dimension of the generalized Petersen graphs \(P(n,m)\) for \(n = 2m+1\) and \(m \geq 1\) and give a partial answer to the question raised in \([9]\): Is \(P(n, m)\) for \(n \geq 7\) and \(3 \leq m \leq \lfloor \frac{n-1}{2} \rfloor\) a family of graphs with constant metric dimension? We prove that the generalized Petersen graphs \(P(n,m)\) with \(n = 2m +1\) have metric dimension \(3\) for every \(m \geq 2\).

Let \(G\) be a graph on \(n\) vertices. \(\delta\) and \(\alpha\) be the minimum degree and independence number of \(G\), respectively. We prove that if \(G\) is a \(2\)-connected graph and \(|N(x) \cup N(y)| \geq n-\delta – 1\) for each pair of nonadjacent vertices \(x,y\) with \(1 \leq |N(x) \cap N(y)| \leq \alpha – 1\), then \(G\) is hamiltonian or \(G \in \{G_1, G_2\}\) (see Figure 1.1 and Figure 1.2). As a corollary, if \(G\) is a 2-connected graph and \(|N(x) \cup N(y)| \geq n – \delta\) for each pair of nonadjacent vertices \(x,y\) with \(1 \leq |N(x) \cap N(y)| \leq \alpha – 1\), then \(G\) is hamiltonian. This result extends former results by Faudree et al. \(([5])\) and Yin \(([7])\).

Arising from the VLSI design and network communication, the cutwidth problem for a graph \(G\) is to embed \(G\) into a path such that the maximum number of overlap edges (i.e., the congestion) is minimized. The characterization of forbidden subgraphs or critical graphs is meaningful in the study of a graph-theoretic parameter. This paper characterizes the set of \(4\)-cutwidth critical trees by twelve specified ones.

A path \(P\) in an edge-colored graph (not necessarily a proper edge-coloring) is a rainbow path if no two edges of \(P\) are assigned the same color. For a connected graph \(G\) with connectivity \(\kappa(G)\) and an integer \(k\) with \(1 \leq k \leq \kappa(G)\), the rainbow \(k\)-connectivity \(rc_k(G)\) of \(G\) is the minimum number of colors needed in an edge-coloring of \(G\) such that every two distinct vertices \(u\) and \(v\) of \(G\) are connected by at least \(k\) internally disjoint \(u-v\)rainbow paths. In this paper, the rainbow \(2\)-connectivity of the Petersen graph as well as the rainbow connectivities of all cubic graphs of order \(8\) or less are determined.

This paper investigates the number of rooted simple bipartite maps on the sphere and presents some formulae for such maps with the number of edges and the valency of the root-face as two parameters.