A Note on the Laplacian Eigenvectors of Threshold Graphs

Irene Sciriha, Zoia Sherman, James L. Borg · 2026

Read A Note on the Laplacian Eigenvectors of Threshold Graphs by Irene Sciriha, Zoia Sherman, James L. Borg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03645.txt.

Introduction

James L. Borg, Irene Sciriha, and Zoia Sherman give a new proof of a striking property of threshold graphs. Threshold graphs can be described in several ways, including as graphs avoiding certain small patterns, or through a finite sequence of positive integers. Their remarkable feature is that all threshold graphs of the same order share a common integer Laplacian eigenbasis.

Having an integer eigenbasis shared across a whole family is unusual, and the property actually characterizes threshold graphs. The result was first proved by Macharete and Del Vecchio. Borg and his co-authors supply a different proof of the same theorem, offering a fresh route through the structure that may suit other arguments.

Catalog record

CREATORIrene Sciriha, Zoia Sherman, James L. Borg
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE27 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.03645

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Note on the Laplacian Eigenvectors of Threshold Graphs Irene Sciriha, Zoia Sherman, James L. Borg Abstract Abstract Threshold graphs are graphs that can be characterized in a number of different ways. For example, they are graphs that are P_{4},\ C_{4},\ 2K_{2} –free. They may also be characterized by a finite sequence of positive integers a_{1},\ldots,a_{r} , such that a_{1}\geqslant 2 and a_{1}+a_{2}+\cdots+a_{r}=|V(G)| . Threshold graphs have the remarkable property that all graphs of the same order share a common integer Laplacian eigenbasis. This property characterizes threshold graphs. This result was proved in [ 12 ] . We give a different proof of the same result. 1 Introduction We consider finite undirected graphs without loops or multiple edges. A graph G=({\mathcal{V}},{\mathcal{E}}) has vertex set {\mathcal{V}}(G) and edge set {\mathcal{E}}(G), where |{\mathcal{V}}|=n and |{\mathcal{E}}|=m . The complement G^{C} of a graph G has the same vertex set as G and its edge set consists of the non–edges of G . The complete graph on n vertices is denoted K_{n} , while K_{1,n-1} denotes the star graph on n vertices. A clique of a graph G is a set of vertices that induce a maximal complete subgraph in G. The same set of vertices induce a coclique in G^{C} . The adjacency matrix of a graph G is a square matrix of size |V(G)|\times|V(G)| , defined by: A(G)_{ij}=\begin{cases}1&\text{if }v_{i}\text{ and }v_{j}\text{ are adjacent }\\ 0&\text{otherwise}.\end{cases} The degree matrix of the graph G , D(G) is the diagonal matrix with D(G)_{ii}= degree of vertex v_{i} . The Laplacian matrix is defined by L(G)=D(G)-A(G). The vertex set of the disjoint union G_{1}\dot{\cup}G_{2} of two graphs G_{1} and G_{2} , is {\mathcal{V}}(G_{1})\cup{\mathcal{V}}(G_{2}) and its edge set is {\mathcal{V}}(G_{1})\cup{\mathcal{V}}(G_{2}). The join G_{1}\vee G_{2} of two graphs G_{1} and G_{2} is (G_{1}^{C}\dot{\cup}G_{2}^{C})^{C}. Threshold graphs are graphs that can be constructed from an isolated vertex by successive disjoint unions and/or joins with other isolated vertices, as explained in Section 2 in more detail. The vertex set is partitioned into r cells corresponding to the r distance vertex degree. The creation sequence of a threshold graph is the sequence of cell sizes. Threshold graphs have been shown to possess fascinating structural and spectral properties [ 16 , 20 , 21 ] . An underlying graph of a threshold graph is the antiregular graph , which consists of r cells of size 1, except the first which is of size 2. A threshold graphs can then be constructed from an antiregular graph with the same number of cells, by increasing the size of cells. Since each Laplacian eigenvalue of an antiregular graph is simple, the Laplacian eigenbasis is unique up to multiples. It is a notable property of threshold graphs, proved in [ 12 ] , that all threshold graphs of the same order share a common eigenbasis of vectors for their Laplacian eigenspaces, which is that of the antiregular graph on the same number of vertices. We give an alternative proof of this theorem in the sequel. The paper is organised as follows. In Section 2, we describe threshold graphs and their construction from creation sequences. In Section 3, we determine spectral properties of the Laplacian matrix of threshold graphs and their associated eigenvectors, and give a new proof of the theorem mentioned above (Theorem 3.4 ). 2 Threshold Graphs 2.1 Basic properties Threshold graphs have been discovered independently by many authors, in a number of different contexts. Initially created by Chvátal and Hammer in relation to the knapsack problem [ 3 ] , threshold graphs were defined as those graphs that admit a weight function w:{\mathcal{V}}\longrightarrow{\mathbb{R}} on the vertices such that there exists a threshold \xi\in{\mathbb{R}} satisfying w(v_{\ell})+w(v_{k})>\xi if and only if \{v_{\ell},v_{k}\}\in{\mathcal{E}} . The smallest subgraphs that do not admit a weight function are 2K_{2} , C_{4} and P_{4} . Interestingly, threshold graphs are also characterized as those graphs that are 2K_{2} , C_{4} and P_{4} free [ 13 , 5 , 6 ] . Their construction can be encoded using a binary sequence. Definition 2.1 . A threshold graph on n vertices is defined by its binary creative sequence (BCS) b_{1},b_{2},\ldots,b_{n}, where b_{1}=b_{2} . An entry 0 in the BCS represents the addition of an isolated vertex while an entry 1 means the addition of a dominating vertex. The entry b_{n} is 1 for a connected threshold graph. Starting from an isolated vertex, a given BCS enables the construction of a unique threshold graph. The entries b_{1} and b_{2} are the same, and they are 1 or 0 depending on whether the first two vertices are, respectively, adjacent or not. A subsequence in the BCS corresponds to a clique if the entries are all equal to 1 and a coclique if they are all equal to 0. Definition 2.2 . A threshold graph C(a_{1},a_{2},\ldots,a_{r}) on n vertices has a compact creative sequence (CCS) of positive integers, a_{1},a_{2},\ldots,a_{r} , obtained from the BCS b_{1},b_{2},\ldots,b_{n} of the threshold graph, such that \sum_{i=1}^{r}a_{i}=n, a_{1}\geq 2, and for 1\leq i\leq r , a_{i} is the length of the i th subsequence of the same value (0 or 1) in BCS. It is clear that in a connected threshold graph, when starting with an isolated vertex, if the second vertex added is a dominating vertex , i.e. a vertex that is adjacent to all the other vertices of the graph, corresponding to entry b_{2}=1, then r is odd, while if b_{2}=0 , then r is even. The threshold graph has r cells where each cell is a clique or a coclique. The degree of each vertex in a cell is the same. Therefore the number of distinct vertex degrees is the number r of cells A_{1},A_{2},\ldots A_{r}, of size a_{1},a_{2},\ldots,a_{r}, respectively. A threshold graph is connected if and only if the subsequence of size a_{r} in the BCS consists of 1 bits. A threshold graph is a split graph, that is, its vertex set can be partitioned into two subsets, one inducing a clique, the other a coclique. A split graph is known to be 2K_{2} , C_{4} and C_{5} –free. Note that P_{4} is a split graph while C_{5} is not a threshold graph. Definition 2.3 . The connected antiregular graph C(2,1,1,\ldots,1) is the threshold graph having r cells with the least number of vertices. The antiregular graph has the maximum possible number of distinct vertex degrees among all connected graphs of order n , as it has only two vertices with the same degree. R. Merris showed that every tree on r+1 vertices is a subgraph of A_{r+1} [ 16 ] . In [ 21 ] , a threshold graph having r cells is constructed from A_{r+1} by blowing up the size of selected cells to reach the cell sizes given by the CCS. Hence we say that a threshold graph with r cells A_{1},\ldots A_{r} has the antiregular graph C(2,1,1,\ldots,1) as an underlying induced subgraph also with r cells. A threshold graph C(a_{1},\ldots,a_{r}),\ a_{1}\geq 2, has r cells A_{1},\ldots,A_{r} that correspond to r distinct degrees. Let N_{i} be the open neighbourhood of each of the vertices in the coclique cell A_{i} . Note that for odd r , each of the a_{2k} vertices in the coclique A_{2k} ,

Read the complete text