In this note, we present some upper bounds for the \(k\)th largest eigenvalue of the adjacency matrix as well as the Laplacian matrix of graphs. Special attention is paid to the Laplacian matrix of trees.

Let \(P(G, \lambda)\) denote the chromatic polynomial of a graph \(G\). Two graphs \(G\) and \(H\) are chromatically equivalent, written \(G \sim H\), if \(P(G, \lambda) = P(H, \lambda)\). A graph \(G\) is chromatically unique, written \(x\)-unique, if for any graph \(H\), \(G \sim H\) implies that \(G\) is isomorphic with \(H\). In this paper, we prove that the graph \(\theta(a_1, a_2, \ldots, a_6)\) is \(x\)-unique for exactly two distinct values of \(a_1, a_2, \ldots, a_6\).

In this paper, we give an explicit expression of the genus distributions of \(M_j^n\), for \(j = 1, 2, \ldots, 11\), which are introduced in the previous paper “Orientable embedding distributions by genus for certain types of non-planar graphs”. For a connected graph \(G = (V, E)\) with a cycle, let \(e\) be an edge on a cycle. By adding \(2n\) vertices \(u_1, u_2,u_3 \ldots, u_n, v_1, v_2,v_3 \ldots, v_n\) on \(e\) in sequence and connecting \(u_k, v_k\) for \(1 \leq k \leq n\), a non-planar graph \(G_n\) is obtained for \(n \geq 3\). Thus, the orientable embedding distribution of \(G_n\) by genus is obtained via the genus distributions of \(M_j^n\).

A graph \(G\) is \(N^m\)-locally connected if for every vertex \(v\) in \(G\), the vertices not equal to \(v\) and with distance at most \(m\) to \(v\) induce a connected subgraph in \(G\). In this note, we first present a counterexample to the conjecture that every \(3\)-connected, \(N^2\)-locally connected claw-free graph is hamiltonian and then show that both connected \(N^2\)-locally connected claw-free graph and connected \(N^3\)-locally connected claw-free graph with minimum degree at least three have connected even \([2, 4]\)-factors.

In J.-P. Serre’s \(Lettre \;à\; M. Tsfasman\) \([3]\), an interesting bound for the maximal number of points on a hypersurface of the \(n\)-dimensional projective space \(PG(n,q)\) over the Galois field \(GF(q)\) with \(q\) elements is given. Using essentially the same combinatorial technique as in \([3]\), we provide a bound which is relative to the maximal dimension of a subspace of \(PG(n,q)\) which is completely contained in the hypersurface. The lower that dimension, the better the bound. Next, by using a different argument, we derive a bound which is again relative to the maximal dimension of a subspace of \(PG(n, q)\) which is completely contained in the hypersurface, If that dimension increases for the latter case, the bound gets better.
As such, the bounds are complementary.

In this paper, it is shown that a variation of banana trees is odd graceful, and it is also proved that the variation of banana is graceful and \(\hat{p}\)-labeling in some cases.

In this paper, we consider the generalized Fibonacci and Pell Sequences and then show the relationships between the generalized Fibonacci and Pell sequences, and the Hessenberg permanents and determinants.

In this paper, a sequence representation of Dyck paths is presented, which yields a sequence representation of the Dyck path poset \({D}\) ordered by pattern containment. This representation makes it clear that the Dyck path poset \({D}\) takes the composition poset investigated by Sagan and Vatter as a subposet, and that the pattern containment order on Dyck paths exactly agrees with a generalized subword order also presented by Sagan and Vatter. As applications of the representation, we describe the Möbius function of \({D}\) and establish the Möbius inverse of the rank function of \({D}\) in terms of Dyck sequences. In the end, a Sperner and unimodal subposet of \({D}\) is given.

A graph is said to be determined by its adjacency spectrum (or to be a DS graph, for short) if there is no other non-isomorphic graph with the same adjacency spectrum. Although all connected graphs of index less than \(2\) are known to be determined by their adjacency spectra, the classification of DS graphs of index less than \(2\) is not complete yet. The purpose of this paper is to characterize all DS graphs of index less than \(2\) with no \(Z_n\) as a component.

Let \(B\) be a bipartite graph. We obtain two new results as follows:(1) Suppose that \(u \in V(B)\) is a vertex such that \(N_B(u)\) contains at least \(|N_B(u)| – 1\) odd vertices. Let \(f : V(B) \to \mathbb{N}\) be the function such that \(f(u) = 1\) and \(f(v) = \lceil d_B(v)/2 \rceil + 1\) for \(v \in V(B) \setminus u\). Then \(B\) is \(f\)-choosable.(2) Suppose that \(u \in V(B)\) is a vertex such that every vertex in \(N_B(u)\) is odd, and \(v \in V(B)\) is an odd vertex that is not adjacent to \(u\). Let \(f : V(B) \to \mathbb{N}\) be the function such that \(f(u) = 1\), \(f(v) = \lceil d_B(v)/2 \rceil\), and \(f(w) = \lceil d_B(w)/2 \rceil + 1\) for \(w \in V(B) \setminus \{u, v\}\). Then \(B\) is \(f\)-choosable.