1 Introduction

Throughout the paper, all graphs are assumed to be finite, undirected and without loops or multiple edges. Cographs were introduced in 1960’s [18], and this class has been rediscovered independently by several authors in many equivalent ways since then. They are intensively studied in the domain of structural considerations, spectral properties and applications. A short background is given in the next section. A cograph is usually defined as a \(P_4\)-free graph, i.e., a graph that does not contain the 4-vertex path as an induced subgraph. It is also known that the class of cographs is closed under taking disjoint unions or complementation, and therefore an alternative definition says that an isolated vertex is a cograph, and if G and H are cographs, then their disjoint union \(G\cup H\) is a cograph and their join \(\overline{{\overline{G}}\cup {\overline{H}}}\) is also a cograph [9]; as usual, an overline designates the complementary graph.

Particular cographs considered in this study are defined in the following way (and the fact that they are cographs follows from the mentioned equivalent definitions). Let \(K_\alpha \) denote the complete graph on \(\alpha \) vertices. For positive integers \(\alpha _1,\alpha _2,\ldots ,\alpha _k\), \(C(\alpha _1,\alpha _2,\ldots ,\alpha _k)\) denotes the cograph defined recursively by

$$\begin{aligned} \left\{ \begin{array}{l} C(\alpha _1)={\overline{K}}_{\alpha _1}, \\ C(\alpha _1,\alpha _2,\ldots ,\alpha _i)=\overline{C(\alpha _1,\alpha _2,\ldots ,\alpha _{i-1})\cup K_{\alpha _i}},~ \text {for}~ 2\le i\le k. \end{array}\right. \end{aligned}$$

Simultaneously, \((\alpha _1, \alpha _2, \ldots , \alpha _k)\) is referred to as the generating sequence of the corresponding cograph. In simple words, to construct \(C(\alpha _1,\alpha _2,\ldots ,\alpha _k)\), we begin with \({\overline{K}}_{\alpha _1}\). In the next step, we take the disjoint union of \(K_{\alpha _2}\) and the graph obtained in the first step, and then take the complementary graph. Proceeding in this way, we finally take the disjoint union of \(K_{\alpha _k}\) and the graph obtained in the \((k-1)\)th step, and finalize the construction by another complementation. Equivalently,

$$\begin{aligned} C(\alpha _1,\alpha _2,\ldots ,\alpha _k)\cong \overline{\overline{\overline{K_{\alpha _1}}\cup K_{\alpha _2}}\cup \cdots \cup K_{\alpha _k}}. \end{aligned}$$

A construction of the 10-vertex cograph C(4, 2, 3, 1) is illustrated in Fig. 1. Let \({\mathcal {C}}\) denote the class of cographs constructed in above way. For \(G\in {\mathcal {C}}\), we simply say that G is a \({\mathcal {C}}\)-graph. In particular, \({\mathcal {C}}_{even}\) denotes the \({\mathcal {C}}\)-graphs that are generated by an even sequence. Accordingly, they are called \({\mathcal {C}}_{even}\)-graphs. In the entire paper our focus is on this particular class, so k is assumed to be even.

Fig. 1
figure 1

Construction of the \({\mathcal {C}}\)-graph C(4, 2, 3, 1)

Full size image

To explain our motivation, we recall that a threshold graph is a \(\{P_4,2K_2, C_4\}\)-free graph, i.e., a particular cograph without an induced subgraph isomorphic to either two parallel edges or the 4-vertex cycle. It is known that every threshold graph is generated by a finite binary sequence [2, 6, 7]. Moreover, the same holds for their bipartite counterparts known as chain graphs [3, 23], not defined here. In this context, an experienced reader will surely recall the every n-vertex tree (even more, a labelled n-vertex tree) is generated by a unique sequence of \(n-2\) numbers called the Prüfer sequence [27]. And, of course, there are other graphs that are, in a similar way, uniquely generated by the corresponding finite sequences. This approach appears to be very convenient since the entire graph is fully determined by a simple sequence; instead of ‘a sequence’, one may also say ‘a vector’ or ‘a string’. Moreover, a generating sequence provides information about many structural and spectral parameters.

In contrast to the aforementioned graph classes, a representation of a \({\mathcal {C}}\)-graph by a finite sequence may or may not be unique; in other words, it may occur that different sequences are associated with the same graph; for example, C(1, 2, 2) and C(1, 1, 1, 2) are isomorphic. However, according to [22], if \(G\in {\mathcal {C}}_{even}\), then there is a unique even sequence \((\alpha _1, \alpha _2, \ldots , \alpha _{2k})\) such that \(G\cong C(\alpha _1,\alpha _2,\ldots ,\alpha _{2k})\). In this paper, we investigate the invariants that can be deduced from the generating sequence of a \({\mathcal {C}}_{even}\)-graph. Here is the outline of the results established in the forthcoming sections.

To give a clear insight into the class \({\mathcal {C}}\) and the subclass \({\mathcal {C}}_{even}\), we first give some data and comparisons with certain related graph classes.

If A is the standard adjacency matrix of a graph G and D is the diagonal matrix of vertex degrees, then \(L=D-A\) is the Laplacian matrix of G. Its eigenvalues, spectrum and eigenvectors are known as the Laplacian eigenvalues, the Laplacian spectrum and the Laplacian eigenvectors of G. In particular, the second smallest Laplacian eigenvalue a(G) is called the algebraic connectivity of G. In this paper, we establish a recurrence formula that computes the Laplacian eigenvalues and the Laplacian eigenvectors of a \({\mathcal {C}}\)-graph in terms of its generating sequence. We also give a lower bound and an upper bound for the number of distinct Laplacian eigenvalues, and for each bound we construct \({\mathcal {C}}_{even}\)-graphs that attain it.

Also, we consider \({\mathcal {C}}_{even}\)-graphs with a fixed number of vertices that either maximize or minimize the algebraic connectivity. It occurs that this invariant is maximized by the complete graph and minimized by the star. In the next natural step, we determine the maximizers and the minimizers within the class of \({\mathcal {C}}_{even}\)-graphs excluding complete graphs and stars.

A clique in a graph is a set of vertices that are adjacent to each other. The size of a maximum clique of a graph G is known as the clique number, denoted by \(\omega (G)\). We give an explicit formula for the clique number of \(G\in {\mathcal {C}}_{even}\), and determine whether \(\omega (G)\) is less than, equal to, or greater than a(G); it appears that the last number \(\alpha _k\) of the corresponding generating sequence is sufficient to establish this comparison.

Concerning related works, cographs have received a great deal of attention in the last six decades. Some notable results that are related to our results are obtained in [24] (where Merris proved that the Laplacian spectrum of every cograph consists entirely of integers), [20] (where Lazzarin et al. proved that no two non-isomorphic equivalent cographs share the same Laplacian spectrum), [1] (where Abrishami proved that for every non-complete cograph the algebraic connectivity and the vertex connectivity are equal), and [4, 5, 8, 13, 14, 16, 25, 28] (where different authors have established many results concerning spectral properties of cographs and related graphs). Many results concerning lower and upper bounds for the algebraic connectivity can be found in [29, Sections 6.6–6.9]. Since, in case of cographs, this invariant coincides with the vertex connectivity, our results also relate the results concerning the bounds for the latter invariant, and some of them can be found in [15, 19, 21]. In a classical paper [17] Karp proved the NP-completeness of 21 combinatorial problems, and one of them is computing the maximal clique. Since then, this problem has been considered for many graph classes, and some results can be found in [12, 26] and references therein.

Section 2 contains data about \({\mathcal {C}}\)-graphs and some preliminary results concerning their Laplacian matrix. In Section 3 we deal with the Laplacian eigenvalues and the corresponding eigenspaces. A range for the number of distinct Laplacian eigenvalues is given in Section 4. The graphs \(G\in {\mathcal {C}}_{even}\) that maximize or minimize a(G) are considered in Section 5. Section 6 is reserved for the clique number of a \({\mathcal {C}}_{even}\)-graph.

2 On \({\mathcal {C}}\)-graphs

By employing a computer search based on generating sequences, we have found more than 1,000 \({\mathcal {C}}\)-graphs with 12 vertices and more than 8,388,600 \({\mathcal {C}}\)-graphs with 25 vertices. However, computing the exact number of \({\mathcal {C}}\)-graphs with a fixed number of vertices seems to be a difficult task, as we have found certain overlapping between \({\mathcal {C}}_{even}\) and \({\mathcal {C}}_{odd}\); for example, C(1, 1, 1, 2) and C(1, 2, 2) represent the same \({\mathcal {C}}\)-graph.

Observe that \(C(n-1,1)\) is the complete graph \(K_n\), whereas \(C(p-1,1,q)\) is the complete bipartite graph \(K_{p,q}\). The following cographs are also categorised as \({\mathcal {C}}\)-graphs.

  • A split graph is a graph whose vertex set admits a partition into a clique and a co-clique. A complete split graph, studied in [10], is a split graph in which every vertex of the co-clique is adjacent to every vertex in the clique. We observe that every complete split graph is a \({\mathcal {C}}\)-graph represented by \(C(\alpha _1,\alpha _2)\). However, the class of \({\mathcal {C}}\)-graphs does not include all split graphs.

  • An antiregular graph is a connected graph whose degree sequence has only two repeated entries. Its representation is either \(C(1,1,\ldots ,1)\) or \(C(1,2,1,1,\ldots ,1)\).

  • A chordal graph is a graph without an induced subgraph isomorphic to the cycle \(C_i,~ i\ge 4\). Therefore, a cograph is a chordal graph if and only if it is \(C_4\)-free. Hence, the \({\mathcal {C}}\)-graph \(C(\alpha _1,\alpha _2,\ldots ,\alpha _{k})\) is chordal whenever \(\alpha _{2i}>1\) holds for at most one i, where \(1\le i\le \frac{k}{2}\). We note in passing that a chordal cograph is also known as a quasi-threshold graph.

There is no inclusion between the class \({\mathcal {C}}\) and the class of threshold graphs. However, concerning binary representations of threshold graphs given in [2, 7], one may deduce that for a fixed number of vertices, the number of \({\mathcal {C}}\)-graphs is never less than the number of threshold graphs. We shall skip the details and note that the same holds in comparison to the classes of chain graphs and complete multipartite graphs.

We recall that the eigenvalues of the Laplacian matrix are non-negative, zero is one of them and its multiplicity is equal to the number of components of a graph [29, Subsection 1.2.2]. We proceed with a particular blocking of the Laplacian matrix. Although our focus is on \({\mathcal {C}}_{even}\)-graphs, the following setting remains valid for all \({\mathcal {C}}\)-graphs. Evidently, a generating sequence \((\alpha _1, \alpha _2, \ldots , \alpha _k)\) of a \({\mathcal {C}}\)-graph provides a partition of its vertex set. Moreover, vertices belonging to the same part share the same degree. In this context, we consider the corresponding equitable partition \(\pi =\{\pi _{\alpha _1}, \pi _{\alpha _2}, \dots ,\pi _{\alpha _k}\}\) such that \(|\pi _{\alpha _i}|=\alpha _i\), for \(1\le i\le k\). Let \(d_{\alpha _i}\) denote the degree of a vertex in \(\pi _{\alpha _i}\). Then we deduce that

$$\begin{aligned} d_{\alpha _i}={\left\{ \begin{array}{ll} \alpha _i-1 +\sum _{j~\text {even},~j \ge i+1}\alpha _j&{}\text {if}~i~\text {is odd},\\ \sum _{j=1}^{i-1}\alpha _j +\sum _{\ell ~\text {even},~ \ell \ge i+2}\alpha _\ell &{}\text {if}~i~\text {is even and}~i<k, \\ \sum _{j=1}^{i-1}\alpha _j, &{} \text {if}~i=k. \end{array}\right. } \end{aligned}$$

Accordingly, the Laplacian matrix of \(C(\alpha _1,\alpha _2,\dots ,\alpha _k)\) admits the following blocking

$$\begin{aligned} L=\begin{bmatrix} (d_{\alpha _1}+1)I-J&{}-J &{}O &{}-J&{} \dots &{} O&{}-J \\ -J&{}d_{\alpha _2}I &{}O &{}-J&{}\dots &{}O&{}-J\\ O&{}O&{}(d_{\alpha _3}+1)I-J&{}-J &{} \dots &{}O&{}-J\\ -J&{}-J&{}-J&{}d_{\alpha _4}I&{}\dots &{}O&{}-J\\ &{} &{} &{} &{} \ddots \\ O&{}O&{}O&{}O&{}\dots &{}(d_{\alpha _{k-1}}+1)I-J&{}-J \\ -J&{}-J&{}-J&{}-J&{} \dots &{}-J&{}d_{\alpha _k}I \end{bmatrix}, \end{aligned}$$
(1)

where I and J denote the identity matrix and the all-1 matrix, respectively.

Consequently the quotient matrix of L, that correspond to \(\pi \), is the \(k\times k\) matrix given by

$$\begin{aligned} Q_L= \begin{bmatrix} d_{\alpha _1}-(\alpha _1-1)&{}-\alpha _2 &{}0 &{}-\alpha _4&{} \dots &{}0&{}- \alpha _k \\ -\alpha _1&{}d_{\alpha _2}&{}0 &{}-\alpha _4&{} \dots &{}0&{}-\alpha _k\\ 0 &{}0&{}d_{\alpha _3}-(\alpha _3-1)&{}-\alpha _4 &{} \dots &{}0&{}-\alpha _k\\ -\alpha _1&{}-\alpha _2&{}-\alpha _3&{}d_{\alpha _4}&{}\dots &{}0&{}-\alpha _k\\ &{} &{} &{} &{} \ddots \\ 0&{}0&{}0&{}0&{}\dots &{}\alpha _k&{}-\alpha _k \\ -\alpha _1&{}-\alpha _2&{}-\alpha _3&{}-\alpha _4&{} \dots &{}-\alpha _{k-1}&{}d_{\alpha _k} \end{bmatrix}. \end{aligned}$$

Every eigenvalue of \(Q_L\) is an eigenvalue of L. To see this it is sufficient to take an eigenvector \({\textbf{x}}=(x_1, x_2, \ldots , x_k)^\intercal \) associated with an eigenvalue \(\lambda \) of \(Q_L\), and construct the vector \((x_1{\textbf{j}}^\intercal _{\alpha _1}, x_2{\textbf{j}}^\intercal _{\alpha _2}, \ldots , x_k{\textbf{j}}^\intercal _{\alpha _k})\), where \({\textbf{j}}_{\alpha _i}\) is the all-1 column of size \(\alpha _i~(1\le i\le k)\). Then the transpose of the obtained vector corresponds to \(\lambda \) in L.

3 Eigenvalues and eigenvectors

We compute the eigenvalues and the eigenvectors of the Laplacian matrix of a \({\mathcal {C}}\)-graph in terms of a generating sequence. Assume that the eigenvalues of the quotient matrix \(Q_L\) are arranged in non-decreasing order as follows:

$$\begin{aligned} 0=\lambda _1 \le \lambda _2 \le \lambda _3 \le \dots \le \lambda _k. \end{aligned}$$
(2)

Theorem 3.1

The eigenvalues of the quotient matrix \(Q_L\) of a \({\mathcal {C}}_{even}\)-graph \(C(\alpha _1,\alpha _2,\dots ,\alpha _k)\), where \(k\ge 4\), are \(\lambda _1=0\), \(\lambda _k=n\) and

$$\begin{aligned} \lambda _i={\left\{ \begin{array}{ll} \lambda _{i-1}+\alpha _{k-2(i-2)}&{}\text {for }2\le i\le \frac{k}{2},\\ \lambda _{i+1}-\alpha _{2i-(k-1)}&{}\text {for }k-1\ge i\ge \frac{k}{2}+1. \end{array}\right. } \end{aligned}$$

Proof

The all-1 vector \({\textbf{j}}\) is associated with \(\lambda _1=0\). We now construct the eigenvectors corresponding to the next \(\frac{k}{2}-1\) smallest eigenvalues as follows:

$$\begin{aligned} {\textbf{x}}_i(j)={\left\{ \begin{array}{ll} 1&{}\text { if }1\le j\le k-2i+2,\\ -\dfrac{\sum _{\ell =1}^{k-2i+2}\alpha _\ell }{\alpha _{k-2i+3}}&{}\text { if } j=k-2i+3,\\ 0&{}\text { otherwise.} \end{array}\right. } \end{aligned}$$

Indeed, for \(i=2\) we have

$$\begin{aligned} {\textbf{x}}_2=\begin{bmatrix} 1&1&1&\cdots&1&-\dfrac{\sum _{\ell =1}^{k-2}\alpha _\ell }{\alpha _{k-1}}&0 \end{bmatrix}^\intercal , \text { along with }Q_L{\textbf{x}}_2=\alpha _k{\textbf{x}}_2, \end{aligned}$$

which implies that \(\alpha _k\) is an eigenvalue of \(Q_L\).

Similarly, for \(i=3\),

$$\begin{aligned} {\textbf{x}}_3=\begin{bmatrix} 1&1&1&\cdots&1&-\dfrac{\sum _{\ell =1}^{k-4}\alpha _\ell }{\alpha _{k-3}}&0&0&0 \end{bmatrix}^\intercal , \text { and }Q_L{\textbf{x}}_3=(\alpha _k+\alpha _{k-2}){\textbf{x}}_3, \end{aligned}$$

which implies that \(\alpha _k+\alpha _{k-2}\) is an eigenvalue of \(Q_L\). In general, for \(2\le i\le \frac{k}{2}\), we obtain

$$\begin{aligned} Q_L{\textbf{x}}_i=(\alpha _k+\alpha _{k-2}+\cdots +\alpha _{k-2(i-2)}){\textbf{x}}_i. \end{aligned}$$

So, \(\alpha _k+\alpha _{k-2}+\cdots +\alpha _{k-2(i-2)}\) is an eigenvalue of \(Q_L\). This establishes the recurrence relation \(\lambda _i=\lambda _{i-1}+\alpha _{k-2(i-2)}.\)

For the remaining eigenvalues, we define vectors

$$\begin{aligned} {\textbf{x}}_{\frac{k}{2}+i}(j)={\left\{ \begin{array}{ll} 1&{}\text { if }1\le j\le 2i-1,\\ -\dfrac{\sum _{\ell =1}^{2i-1}\alpha _\ell }{\alpha _{2i}}&{}\text { if } j=2i,\\ 0&{}\text { otherwise.} \end{array}\right. }. \end{aligned}$$

Now, for \(i=\frac{k}{2}\), we obtain

$$\begin{aligned} {\textbf{x}}_k=\begin{bmatrix} 1&1&1&\cdots&1&-\dfrac{\sum _{\ell =1}^{k-1}\alpha _\ell }{\alpha _{k}} \end{bmatrix}^\intercal , \text { and }Q_L{\textbf{x}}_k=\Big (\sum _{\ell =1}^k\alpha _\ell \Big ){\textbf{x}}_k=n{\textbf{x}}_k, \end{aligned}$$

Therefore, the largest eigenvalue of \(Q_L\) is n. In general, for \(1\le i\le \frac{k}{2}\), it holds

$$\begin{aligned} Q_L{\textbf{x}}_{\frac{k}{2}+i}=\Big (\sum _{\ell =1}^{k/2}\alpha _{2\ell }+\sum _{m=1}^i\alpha _{2m-1}\Big ) {\textbf{x}}_{\frac{k}{2}+i}, \end{aligned}$$

which concludes the proof. \(\square \)

The following theorem gives the remaining eigenvalues of L.

Theorem 3.2

The remaining \(n-k\) eigenvalues of L are \(d_{\alpha _{2i}}\) with multiplicity \(\alpha _{2i}-1\) and \(d_{\alpha _{2i-1}}+1\) with multiplicity \(\alpha _{2i-1}-1\), for \(i\le \frac{k}{2}\).

Proof

For \(\ell >1\), let \(\{E_j^\ell \}\) denote the set of orthogonal of \(\ell -1\) row-vectors in \({\mathbb {R}}^\ell \) defined by

$$\begin{aligned} E_j^\ell ={\varvec{{e}}}_1(\ell )+{\varvec{{e}}}_2(\ell )+\cdots +{\varvec{{e}}}_{j}(\ell )-j{\varvec{{e}}}_{j+1}(\ell ),\, \text {for all}~j~\text {such that}~ 1\le j\le \ell -1, \end{aligned}$$

where \({\textbf {e }}_{j}(\ell )\) is the jth row-vector of the canonical basis of \({\mathbb {R}}^\ell \).

Now, for every \(\alpha _i\ge 2\), we define

$$\begin{aligned} {\textbf{x}}_j^{\alpha _i}=[{\textbf{0}}_{\alpha _1}\ {\textbf{0}}_{\alpha _2}\ \cdots \ {\textbf{0}}_{\alpha _{i-1}}\ E_j^{\alpha _i} \ {\textbf{0}}_{\alpha _{i+1}}\ \cdots \ {\textbf{0}}_{\alpha _k}]^\intercal ,\ \ 1\le j \le \alpha _i-1,\,1\le i\le k, \end{aligned}$$

where the \({\textbf{0}}_r\) denotes the all-0 row-vector in \({\mathbb {R}}^r\).

Then, for \(\alpha _i\ge 2\) and \(1\le s \ne t\le \alpha _i-1\), we have

$$\begin{aligned} \big ({\textbf{x}}_s^{\alpha _i}\big )^\intercal {\textbf{x}}_t^{\alpha _i}=E_s^{\alpha _i}\big (E_t^{\alpha _i}\big )^\intercal =0. \end{aligned}$$

Therefore, the set \(\{{\textbf{x}}_1^{\alpha _i},{\textbf{x}}_2^{\alpha _i},\ldots , {\textbf{x}}_{\alpha _{2i-1}}^{\alpha _i}\}\) is orthogonal for all \(\alpha _i\ge 2\). Observe that, in one hand, by (1) the Laplacian L is a \(k\times k\) block matrix whose non-diagonal blocks are constant matrices, while on the other hand, the entry-sum of \(E_j^{\alpha _i}\) is 0 whenever \(\alpha _i\ge 2, 1\le j\le \alpha _i-1\). Thus if \( 1\le i\le k\), for each \(\alpha _{2i}\ge 2\), we obtain

$$\begin{aligned} L{\textbf{x}}_j^{\alpha _{2i}}&=[{\textbf{0}}_{\alpha _1}\ {\textbf{0}}_{\alpha _2}\ \cdots \ {\textbf{0}}_{\alpha _{i-1}}\ d_{\alpha _{2i}}E_j^{\alpha _i} \ {\textbf{0}}_{\alpha _{i+1}}\ \cdots \ {\textbf{0}}_{\alpha _k}]^\intercal =d_{\alpha _{2i}}{{\textbf{x}}_j^{\alpha _{2i}}}, \end{aligned}$$

for all \(1\le j\le \alpha _{2i}-1.\)

Similarly, for \(\alpha _{2i-1}\ge 2\), the vectors \( {\textbf{x}}_j^{\alpha _{2i-1}}\) satisfy

$$\begin{aligned} L{\textbf{x}}_j^{\alpha _{2i-1}}=(d_{\alpha _{2i-1}}+1){{\textbf{x}}_j^{\alpha _{2i-1}}},\ \ \text { for } 1\le j\le \alpha _{2i}-1, \end{aligned}$$

and this completes the proof. \(\square \)

We provide more details in a particular case \(k=2\). Despite it is simple, this case is illustrative since it computes the eigenvectors according to the previous theorems. Also, it will be used in the sequel.

Example 3.3

For \(k=2\), the corresponding \({\mathcal {C}}_{even}\)-graph is the complete split graph \(C(\alpha _1,\alpha _2)\). The quotient matrix \(Q_L\) is

$$\begin{aligned} Q_L= \begin{bmatrix} d_{\alpha _1}-(\alpha _1-1)&{}-\alpha _2 \\ -\alpha _1&{}d_{\alpha _2} \end{bmatrix}=\begin{bmatrix} \alpha _2&{}-\alpha _2 \\ -\alpha _1&{}\alpha _1 \end{bmatrix} \end{aligned}$$

Its eigenvalues are \(\lambda _1=0\) an \(\lambda _2=\alpha _1+\alpha _2\). The remaining two eigenvalues of L are \(d_{\alpha _2}\) with multiplicity \((\alpha _2-1)\) and \(d_{\alpha _1}+1\) with multiplicity \((\alpha _1-1)\). In the particular case \(\alpha _1=\alpha _2=1\) we deal with a 2-vertex graph with Laplacian eigenvalues 0 and 2. For \(\alpha _1,\alpha _2 \ge 2\), let \({\textbf{x}}_i\), \(1\le i\le (\alpha _2-1)\), and \({\textbf{y}}_j\), \(1\le j\le (\alpha _1-1)\), be the eigenvectors associated with \(d_{\alpha _2}\) and \(d_{\alpha _1}+1\), respectively. Then,

$$\begin{aligned} \begin{array}{c} {\textbf{x}}_1=[\underbrace{0 ~ 0~\cdots ~0}_{\alpha _1} ~1~-1~0~0~\cdots ~0]^\intercal ,\\ {\textbf{x}}_2=[\underbrace{0 ~0~ \cdots ~0}_{\alpha _1}~1~1~-2~ 0~0~ \cdots ~0 ]^\intercal ,\\ {\textbf{x}}_3=[\underbrace{0 ~0~ \cdots ~0}_{\alpha _1}~1~1~1~-3~ 0~0~ \cdots ~0 ]^\intercal ,\\ \vdots \\ {\textbf{x}}_{\alpha _2-1}=[\underbrace{0 ~0~ \cdots ~0}_{\alpha _1}~\underbrace{1~1~\cdots ~1}_{{\alpha _2-1}}~-(\alpha _2-1) ]^\intercal . \end{array} \end{aligned}$$

Similarly,

$$\begin{aligned} \begin{array}{c} {\textbf{y}}_1=[1~-1~ 0~0~\cdots ~0 ~\underbrace{0~0~\cdots ~0}_{\alpha _2}]^\intercal ,\\ {\textbf{y}}_2=[1~1~-2~ 0~0~\cdots ~0 ~\underbrace{0~0~\cdots ~0}_{\alpha _2}]^\intercal ,\\ {\textbf{y}}_3=[1~1~1~-3~ 0~0~\cdots ~0 ~\underbrace{0~0~\cdots ~0}_{\alpha _2}]^\intercal ,\\ \vdots \\ {\textbf{y}}_{\alpha _1-1}=[\underbrace{1~1~\cdots ~1}_{\alpha _1-1}~-(\alpha _1-1)~ \underbrace{0~0~\cdots ~0}_{\alpha _2}]^\intercal . \end{array} \end{aligned}$$

We now provide two straightforward consequences of the previous results. The first one follows directly.

Corollary 3.4

The matrix \(Q_L\) has simple eigenvalues.

Corollary 3.5

The algebraic connectivity of a \({\mathcal {C}}_{even}\)-graph \(G\cong C(\alpha _1,\alpha _2,\dots ,\alpha _k)\) is

$$\begin{aligned} a(G)={\left\{ \begin{array}{ll} \alpha _1&{}\text {if }k=2~\text {and }~\alpha _2\ne 1,\\ \alpha _1+\alpha _2 &{} \text {if }k=2~\text {and}~\alpha _2=1,\\ \min \{\alpha _k,n-\alpha _k\}&{}\text {if } k\ge 4. \end{array}\right. } \end{aligned}$$

Proof

If \(k=2\), then G is a complete split graph \(C(\alpha _1, \alpha _2)\) with Laplacian eigenvalues \( (\alpha _1+\alpha _2)^{\alpha _1}, \alpha _1^{\alpha _2-1}\) and 0, where exponents stand for the multiplicities. Clearly, the second smallest eigenvalue is \(\alpha _1\) when \(\alpha _2\ne 1\), and \(\alpha _1+\alpha _2\) when \(\alpha _2=1\).

If \(k\ge 4\), then, by Theorems 3.1 and 3.2 , the second smallest eigenvalue of G is either \(\alpha _k\), or \(d_{\alpha _{2i}}\) for some \(\alpha _{2i}\ge 2\), or \(d_{\alpha _{2i-1}}+1\) for some \(\alpha _{2i-1}\ge 2\). Here we observe that, \(d_{\alpha _{2i}}>\alpha _{k}\) for all \(1\le i\le k-1\) and \(d_{\alpha _{2i-1}}+1>\alpha _k\) for all \(1\le i\le k\). Therefore, a(G) is either \(\alpha _k\) or \(d_{\alpha _{k}}=n-\alpha _k\) with \(\alpha _k\ne 1\). Now, \(d_{\alpha _k}\ge \alpha _k\) gives \(\alpha _k\ge \frac{n}{2}>1\), so in this case \(n-\alpha _k\) occurs in the spectrum of L. Therefore \(a(G)=\min \{\alpha _k,n-\alpha _k\}\), as desired. \(\square \)

We conclude the section with another example.

Example 3.6

Let us consider the \({\mathcal {C}}_{even}\)-graph C(8, 3, 4, 2, 1, 5, 6, 3, 7, 9) with 48 vertices. The quotient matrix \(Q_L\) is the \(10 \times 10\) matrix given by

$$\begin{aligned} Q_L=\begin{bmatrix} 22&{}-3 &{}0 &{}-2&{}0 &{}-5&{}0&{}-3 &{} 0&{}-9 \\ -8&{}27 &{}0 &{}-2&{}0&{}-5&{}0&{}-3&{}0&{}-9\\ 0&{}0&{}19&{}-2 &{}0 &{}-5&{} 0&{}-3&{}0&{}-9\\ -8&{}-3&{}-4&{}32&{}0&{}-5&{}0&{}-3&{}0&{}-9\\ 0&{}0&{}0&{}0&{}17&{}-5&{}0&{}-3&{}0&{}-9\\ -8&{}-3&{}-4&{}-2&{}-1&{}30&{}0&{}-3&{}0&{}-9\\ 0&{}0 &{}0 &{}0 &{}0 &{}0 &{}12&{}-3&{}0&{}-9 \\ -8&{}-3&{}-4&{}-2&{}-1&{}-5&{}-6&{}38&{}0&{}-9\\ 0&{}0&{}0&{}0&{}0&{}0&{}0&{}0&{}9&{}-9 \\ -8&{}-3&{}-4&{}-2&{}-1&{}-5&{}-6&{}-3&{}-7&{}39 \end{bmatrix}. \end{aligned}$$

By Theorem 3.1, the eigenvalues of \(Q_L\) are 48, 41, 35, 34, 30, 19, 17, 12, 9, 0, while the corresponding eigenvectors are the following ones (a subscript denotes the eigenvalue):

$$\begin{aligned}{} & {} {\textbf{x}}_{48}=[1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1 -\frac{13}{3}]^\intercal ,~~{\textbf{x}}_{0}=[1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ 1]^\intercal , \\{} & {} {\textbf{x}}_{41}=[1\ 1\ 1\ 1\ 1\ 1\ 1\ -\frac{29}{3}\ 0\ 0]^\intercal ,~~{\textbf{x}}_{9}=[1\ 1\ 1\ 1\ 1\ 1\ 1\ 1\ -\frac{32}{7}\ 0]^\intercal , \\{} & {} {\textbf{x}}_{35}=[1\ 1\ 1\ 1\ 1, -\frac{18}{5} 0\ 0\ 0\ 0]^\intercal ,~~{\textbf{x}}_{12}=[1\ 1\ 1\ 1\ 1\ 1\ -\frac{23}{6}\ 0\ 0\ 0]^\intercal , \\{} & {} {\textbf{x}}_{34}=[1\ 1\ 1\ -\frac{15}{2}\ 0\ 0\ 0\ 0\ 0\ 0]^\intercal ,~~{\textbf{x}}_{17}=[1\ 1\ 1\ 1\ -17\ 0\ 0\ 0\ 0\ 0]^\intercal , \\{} & {} {\textbf{x}}_{30}=[1\ -\frac{8}{3}\ 0\ 0\ 0\ 0\ 0\ 0\ 0\ 0]^\intercal ,~~{\textbf{x}}_{19}=[1\ 1\ -\frac{11}{4}\ 0\ 0\ 0\ 0\ 0\ 0\ 0]^\intercal . \end{aligned}$$

Using Theorem 3.2, we compute the remaining eigenvalues and their multiplicities: \(27^2,32,30^4,38^2,39^8,30^7,23^3,\) \(18^5,16^6 \). The corresponding eigenvectors are computed as in Example 3.3.

4 Number of distinct eigenvalues

This section is devoted to the number of distinct eigenvalues, denoted by s(G), of the Laplacian matrix of a \({\mathcal {C}}_{even}\)-graph G. We start with the following theorem.

Theorem 4.1

For a \({\mathcal {C}}_{even}\)-graph \(C(\alpha _1,\alpha _2,\ldots ,\alpha _k)\),

$$\begin{aligned} k\le s(G)\le 2k-1. \end{aligned}$$
(3)

Proof

By Corollary 3.4, the quotient matrix \(Q_L\) has exactly k distinct eigenvalues. Thus, it follows that \(s(G)\ge k\).

Theorem 3.2 says that \(d_{\alpha _{2i}}\) and \(d_{\alpha _{2i-1}}+1\) are the eigenvalues for all \(1\le i\le \frac{k}{2}\); this gives at most k distinct eigenvalues in the spectrum of L. In addition, \(Q_L\) has k distinct eigenvalues. Together, we have at most 2k distinct eigenvalues. However, we observe that \((\frac{k}{2}+1)\)th eigenvalue of \(Q_L\) is always equal to \(d_{\alpha _1}+1\). Thus we obtain \(s(G)\le 2k-1\), and this proves the right-hand side of (3). \(\square \)

In the next two remarks, we will see that the obtained bounds for s(G) are sharp.

Remark 4.2

We observe that the lower bound of (3) is attained in each of the following cases:

  1. 1.

    Let \(G\cong C(\alpha _1,1,1,\ldots ,1)\). Here, \(Q_L\) has k distinct eigenvalues and \(d_{\alpha _1}+1\) is an additional eigenvalue of L. However, \(d_{\alpha _1}+1\) belongs to the spectrum of \(Q_L\), as mentioned in the previous proof. Therefore, G has exactly k distinct eigenvalues.

  2. 2.

    Let \(G\cong C(1,1,\ldots ,1, p, 1)\), with \(2\le p\le \frac{k}{2}-2\). Then, by Theorem 3.2, \(d_{\alpha _{k-1}}+1\) is an eigenvalue of L, but it equals the \((p+2)\)th eigenvalue of \(Q_L\). As before, G has exactly k distinct eigenvalues.

  3. 3.

    Let \(G\cong C(\alpha _1,\alpha _2,\alpha _3,\alpha _4)\). First, note that the eigenvalues of \(Q_L\) are 0, \(\alpha _4\), \(\alpha _1+\alpha _2+\alpha _4=d_{\alpha _1}+1\) and n. Thus if G has exactly 4 distinct eigenvalues, then any eigenvalue of L obtained by Theorem 3.2 must be equal to either \(\alpha _4\) or \(\alpha _1+\alpha _2+\alpha _4\). In this case, G is one of the following (in all cases, \(\alpha \ge 1\)):

    1. (a)

      \(G\cong C(\alpha ,1,1,1)\)

    2. (b)

      \(G\cong C(\alpha ,1,1+\alpha ,1)\)

    3. (c)

      \(G\cong C(\alpha ,1,1,2+\alpha )\)

    4. (d)

      \(G\cong C(\alpha ,1,1+\alpha ,1+\alpha )\)

    5. (e)

      \(G\cong C(\alpha ,1,1+\alpha ,2+2\alpha )\)

    This item also characterizes all \({\mathcal {C}}_{even}\)-graphs with exactly four distinct eigenvalues.

Remark 4.3

Here are some \({\mathcal {C}}_{even}\)-graphs attaining the upper bound of (3):

  1. 1.

    Let G (\(\not \cong K_n\)) be the complete split graph \(C(\alpha _1, \alpha _2)\). The eigenvalues of L are

    $$\begin{aligned} (\alpha _1+\alpha _2)^{\alpha _1}, \alpha _1^{\alpha _2-1}, 0, \end{aligned}$$

    and so the upper bound of (3) is attained. Observe also that this item characterizes all \({\mathcal {C}}_{even}\)-graphs with exactly three distinct eigenvalues.

  2. 2.

    Let \(G\cong C(p,q,p+1,q+1)\), where \(p\ne q\) and \(q>1\). The eigenvalues of L are

    $$\begin{aligned} 2p+2q+2,\ (p+2q+1)^p,\ q+1,\ 0,\ (p+q+1)^{q-1},\ (2p+q+1)^q,\ (p+q+2)^p, \end{aligned}$$

    along with the desired conclusion.

  3. 3.

    Similarly, for \(G\cong C(i,j,r,i+1,j+1,r+1)\), where \(j>1\), \(i\ne r\) and \(r+i\ne j\), by Theorems 3.1 and 3.2 , the eigenvalues of L are \(2i+2j+2r+3,~2i+j+2r+2,~r+i+2,~r+1,~0,~(2i+r+2)^{j-1},~(i+j+2r+1)^i,~(2i+2j+r+2)^r,~(2i+j+r+2)^{i},~(2r+i+2)^{r-1},~(j+r+2)^j\). Hence, \(s(G)=2k-1=11.\)

Next we consider a particular case based on a constant sequence.

Theorem 4.4

Let \(G\cong C(\underbrace{p, p,\ldots , p}_k)\) be a \({\mathcal {C}}_{even}\)-graph, where \(p\ne 1\). Then \(s(G)=k+1.\)

Proof

Let \(\lambda _1,\lambda _2,\ldots ,\lambda _k\) be the eigenvalues of \(Q_L\), arranged as in (2). By Theorem 3.2, G has \(\frac{k}{2}\) eigenvalues of the form \(d_{\alpha _{2i}}\) and \(\frac{k}{2}\) eigenvalues of the form \(d_{\alpha _{2i-1}}+1\). We note the following overlapping between the eigenvalues:

$$\begin{aligned}{} & {} d_{\alpha _2}=d_{\alpha _3}+1, \\{} & {} d_{\alpha _4}=d_{\alpha _1}+1=\lambda _{\frac{k}{2}+1}, \\{} & {} d_{\alpha _{k-i}}=\lambda _{k-(\frac{i}{2}+1)} , ~\text {for}~i\in \{0,2,4,\ldots , k-4\}, \\{} & {} d_{\alpha _{k-j}}+1=\lambda _{k-(\frac{3-j}{2}+6)} , ~\text {for}~j\in \{1,3,5,\ldots , k-5\}. \end{aligned}$$

Therefore, the eigenvalues of \(Q_L\) contribute k to s(G), and the eigenvalues of the form \(d_{\alpha _{2i}}\) (\(\ne d_{\alpha _2}\)) and \(d_{\alpha _{2i-1}}+1\) do not contribute anything extra to s(G); however, \(d_{\alpha _2}\) contributes one. Hence, \(s(G)=k+1\). \(\square \)

The following table contains a list of some \({\mathcal {C}}_{even}\)-graphs with 24 vertices along with their distinct eigenvalues.

Table 1 Distinct eigenvalues of some \({\mathcal {C}}_{even}\)-graphs
Full size table

5 Connectivity

The algebraic connectivity \(a(K_n)\) of a complete graph \(K_n\) is n, and we know from [11, 29] that this graph maximizes the algebraic connectivity in the set of all graphs with n vertices. The vertex connectivity \(\kappa =\kappa (G)\) is maximized by the same graph [11] and it equals \(n-1\). The classical result of Fiedler [11] states that

$$\begin{aligned} a(G)\le \kappa (G)\le \delta (G), \end{aligned}$$

holds for every connected non-complete graph, where \(\delta \) denotes the minimum vertex degree. Moreover, we have pointed out in the first section that, in case of cographs, the first equality is attained. We easily obtain cographs that minimize the algebraic connectivity.

Lemma 5.1

For any connected cograph G, a(G) is an integer and \(a(G)\ge 1.\) If G is a star \(K_{1, n-1}, n\ge 3\), then \(a(G)=1\).

Proof

First, a(G) is an integer since the Laplacian eigenvalues of G are integral. Since G is connected, it holds \(a(G)\ge 1\). For a star with at least three vertices, we have \(a(K_{1, n-1})= \kappa (K_{1, n-1})=1\), which concludes the proof. \(\square \)

In what follows we determine connected non-complete \({\mathcal {C}}_{even}\)-graphs with a fixed number of vertices that maximize the algebraic connectivity, and we also determine connected \({\mathcal {C}}_{even}\)-graphs with a fixed number of vertices that are not stars and minimize the algebraic connectivity.

Theorem 5.2

Among all connected non-complete \({\mathcal {C}}_{even}\)-graphs with n vertices, the graph \(C(n-2,2)\) maximizes the algebraic connectivity.

Proof

Let \(G\cong C(\alpha _1,\alpha _2,\ldots , \alpha _k)\) be a connected non-complete \({\mathcal {C}}_{even}\)-graph. First note that for \(k=2\), the algebraic connectivity is maximized by \(C(n-2,2)\), along with \(a(C(n-2,2))=n-2\), see Example 3.3. For \(k\ge 4\), Corollary 3.5 gives \(a(G)=\min \{\alpha _k, n-\alpha _k\}< n-2\), since \(\alpha _i\ge 1\) for all i. \(\square \)

Theorem 5.3

Among all connected \({\mathcal {C}}_{even}\)-graphs that are non-isomorphic to the star and have n vertices, the graph \(C(\alpha _1,\alpha _2,\ldots , \alpha _{k-2},\alpha _{k-1},1),\ k\ge 4\), minimizes the algebraic connectivity.

Proof

Let \(G\cong C(\alpha _1,\alpha _2,\ldots , \alpha _k)\) be the graph under consideration, and set first \(k\ge 4\). By Corollary 3.5, we have \(a(G)=\min \{\alpha _k, n-\alpha _k\}\), and the desired result follows. It remains to show that \(a(G)>1\) holds for \(k=2\). Applying Corollary 3.5, under the restrictions given in the formulation of this statement, we obtain the required inequality. \(\square \)

Observe that the complete split graph G that is not a star minimizes the algebraic connectivity if and only if \(G\cong {C(2, n-2)}\), which is a direct consequence of Corollary 3.5.

6 Clique number

In this section we compute the clique number of a \({\mathcal {C}}_{even}\)-graph and establish a relationship with the algebraic connectivity.

Theorem 6.1

Let \(G=C(\alpha _1,\alpha _2,\ldots ,\alpha _k)\) be a \({\mathcal {C}}_{even}\)-graph. Then its clique number is

$$\begin{aligned} \omega (G)=\max _{1\le i\le \frac{k}{2}}\Big \{ \alpha _{2i-1}+\frac{k}{2}-i+1\Big \}. \end{aligned}$$

Proof

Consider the equitable partition \(\pi \) of G (defined in Section 2). The vertices of \(\pi _i\) form a clique if i is odd, whereas if i is even then they form a co-clique (that is an edgeless graph). Further, every vertex of \(\pi _{2i-1}\), \(1\le i\le \frac{k}{2}\), is adjacent to every vertex of \(\pi _{2j}\) whenever \(j\ge i\). Therefore, a clique in G is formed by taking \(\alpha _{2i-1}\) vertices of \(\pi _{2i-1}\) together with one vertex from each of \(\pi _{2j}\), where \(j\ge i\). Clearly, such a clique counts \(\alpha _{2i-1} + \frac{k}{2}-i+1\) vertices. The maximum clique is obtained by taking the maximum over \(i~(1\le i\le \frac{k}{2})\), which brings us to the desired result. \(\square \)

The following corollaries are immediate applications of Theorem 6.1.

Corollary 6.2

For the complete split graph \(C(\alpha _1,\alpha _2)\), we have \(\omega (C(\alpha _1,\alpha _2))=\alpha _1+1.\)

Corollary 6.3

For the antiregular graph \(C(1,1,\ldots ,1)\), we have \(\omega (C(1,1,\ldots ,1))=\frac{k}{2}+1.\)

We also emphasize the following result.

Corollary 6.4

For \(k\ge 4\) and a \({\mathcal {C}}_{even}\)-graph \(G\cong C(\alpha _1, \alpha _2, \ldots , \alpha _k)\) with n vertices, we have \(\omega (G)\le n-\alpha _k\), with equality if and only if \(k=4\) and \(\alpha _j=1\) for \(2\le j\le 4\).

Proof

For \(1\le i\le \dfrac{k}{2}\), we have

$$\begin{aligned} n-\alpha _k=\sum _{j=1}^{k-1}\alpha _j\ge \alpha _{2i-1}+k-2\ge \alpha _{2i-1}+\frac{k}{2}-i+1, \end{aligned}$$
(4)

where the first inequality follows from \(\alpha _j\ge 1\) for every j, and the second one follows from \(k\ge 4\). Together with Theorem 6.1, this gives \(\omega (G)\le n-\alpha _k\).

If the equality holds, then we have equalities in (4). The former one yields \(\alpha _j=1\) for \(j\ne 2i-1\). The latter one gives \(k-2=\frac{k}{2}-i+1\), that is \(k-6+2i=0\), which yields \(k=4\) and \(i=1\). Therefore, \(G\cong C(\alpha _1, 1, 1 ,1)\). The opposite implication follows directly. \(\square \)

In case of a complete split graph, the clique number and the algebraic connectivity are computed easily, by employing Corollaries 3.5 and 6.2 . The next result relates these invariants for the remaining \({\mathcal {C}}_{even}\)-graphs.

Theorem 6.5

Let \(G\cong C(\alpha _1, \alpha _2, \ldots , \alpha _k)\) for \(k\ge 4\). Then

$$\begin{aligned} \omega (G){\left\{ \begin{array}{ll}<a(G)&{}\text {if } \omega (G)<\alpha _k,\\ =a(G)&{}\text {if } \omega (G)=\alpha _k,\\>a(G)&{}\text {if } \omega (G)>\alpha _k. \end{array}\right. } \end{aligned}$$
Table 2 A comparison between the clique number and the algebraic connectivity of some random \({\mathcal {C}}_{even}\)-graphs
Full size table

Proof

Assume that \(\alpha _k<n-\alpha _k\). In this case, by Corollary 3.5, we have \(a(G)=\alpha _k\), which establishes the desired result.

For \(\alpha _k\ge n-\alpha _k\), we have

$$\begin{aligned} \omega (G)<n-\alpha _k=a(G)\le \alpha _k, \end{aligned}$$

where the first inequality follows from Corollary 6.4, and the remaining two follow from Corollary 3.5. The last chain of inequalities gives the desired result. \(\square \)

We proceed with particular cases that illustrate the result of the previous theorem.

Corollary 6.6

For each of the following \({\mathcal {C}}_{even}\)-graphs G, the inequality \(\omega (G)>a(G)\) holds:

  1. 1.

    \(G\cong C(\alpha _1, \alpha _2)\), with \(\alpha _2\ge 2\).

  2. 2.

    \(G\cong C(\underbrace{p, p, \ldots , p}_k)\), with \(k\ge 4\).

  3. 3.

    \(G\cong C(\underbrace{\alpha , \beta ,\alpha , \beta , \ldots , \alpha , \beta }_{k\ge 4})\), with \(\alpha >\beta \).

Corollary 6.7

For \(G\cong C(\alpha ,\alpha +1,\ldots , \alpha +k-1)\), with \(k\ge 4\), we have \(\omega (G)=a(G).\)

Corollary 6.8

For \(G\cong C(\alpha ,\alpha ^2,\ldots , \alpha ^k)\), with \(k\ge 4\) and \(\alpha >1\), we have \(\omega (G)<a(G).\)

We conclude this section with a review of \({\mathcal {C}}_{even}\) graphs illustrating how the clique number and the algebraic connectivity may differ from one another. They are given in Table 2.