In this paper, we use a simple method to derive different recurrence relations on the recursive sequence order-\(k\) and their sums, which are more general than that given in literature [J.Feng, More Identities on the Tribonacci Numbers, Ars Combinatoria, \(100(2011), 73-78]\). By using the generating matrices, we get more identities on the recursive sequence order-\(k\) and their sums, which are more general than that given in literature [E.Kihg, Tribonacci Sequences with Certain Indices and Their Sums, Ars Combinatoria, \(86(2008), 13-22]\) .

By applying discharging methods and properties of critical graphs, we proved that every simple planar graph \(G\) with \(\Delta(G) \geq 5\) is of class 1, if any 4-cycle is not adjacent to a 5-cycle in \(G\).

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])\).