A graph \(G\) is pancyclic if it contains a cycle of every length from 3 to \(|V(G)|\) inclusive. A graph \(G\) is panconnected if there exists a path of length \(l\) joining any two different vertices \(x\) and \(y\) with \(d_G(x,y) \leq l \leq |V(G)| – 1\), where \(d_G(x,y)\) denotes the distance between \(x\) and \(y\) in \(G\). A hamiltonian graph \(G\) is panpositionable if for any two different vertices \(x\) and \(y\) of \(G\) and any integer \(k\) with \(d_G(x,y) \leq k \leq |V(G)|/2\), there exists a hamiltonian cycle \(C\) of \(G\) with \(d_C(x,y) = k\), where \(d_C(x,y)\) denotes the distance between \(x\) and \(y\) in a hamiltonian cycle \(C\) of \(G\). It is obvious that panconnected graphs are pancyclic, and panpositionable graphs are pancyclic.

The above properties can be studied in bipartite graphs after some modification. A graph \(H = (V_0 \cup V_1, E)\) is bipartite if \(V(H) = V_0 \cup V_1\) and \(E(H)\) is a subset of \(\{(u,v) | u \in V_0 \text{ and } v \in V_1\}\). A graph is bipancyclic if it contains a cycle of every even length from 4 to \(2\lfloor |V(H)|/2 \rfloor\) inclusive. A graph \(H\) is bipanconnected if there exists a path of length \(l\) joining any two different vertices \(x\) and \(y\) with \(d_H(x,y) \leq l \leq |V(H)| – 1\), where \(d_H(x,y)\) denotes the distance between \(x\) and \(y\) in \(H\) and \(l – d_H(x,y)\) is even. A hamiltonian graph \(H\) is bipanpositionable if for any two different vertices \(x\) and \(y\) of \(H\) and for any integer \(k\) with \(d_H(x,y) \leq k \leq |V(H)|/2\), there exists a hamiltonian cycle \(C\) of \(H\) with \(d_C(x,y) = k\), where \(d_C(x,y)\) denotes the distance between \(x\) and \(y\) in a hamiltonian cycle \(C\) of \(H\) and \(k – d_H(x,y)\) is even. It can be shown that bipanconnected graphs are bipancyclic, and bipanpositionable graphs are bipancyclic.

In this paper, we present some examples of pancyclic graphs that are neither panconnected nor panpositionable, some examples of panconnected graphs that are not panpositionable, and some examples of graphs that are panconnected and panpositionable, for nonbipartite graphs. Corresponding examples for bipartite graphs are discussed. The existence of panpositionable (or bipanpositionable, resp.) graphs that are not panconnected (or bipanconnected, resp.) is still an open problem.

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.