Skip to main content
added 1 character in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, the cocktail party graphs and $K_{n,n,n}$ are determined by the spectra of their adjacency matrix. See for example, Proposition 6 of the paper Which graphs are determined by their spectrum? by van Dam and Haemers. Proposition 6 shows that the disjoint union of any collection of cliques is DS. You also need to use the fact that if $G$ is regular, than a graph is DS with respect to the adjacency matrix if and only if the complement of $G$ is DS with respect to the adjacency matrix. Since the cocktail party graphs and $K_{n,n,n}$ are both regular and the complement of a disjoint union of cliques, the result follows.

Since the paper appears to be behind a paywall, I will include a proof of Proposition 6 here.

Every graph which is the disjoint union of cliques is determined by the spectra of its adjacency matrix.

Proof. Let $G=K_{n_1} \sqcup \dots \sqcup K_{n_k}$ where $n_1 + \dots n_k=n$$n_1 + \dots +n_k=n$. The spectra of $G$ is $n_1-1, \dots, n_k-1, -1, \dots, -1$, where $-1$ occurs $n-k$ times. Let $H$ be a graph with the same spectra and $A$ be the adjacency matrix of $H$. Since all eigenvalues of $A+I$ are nonnegative, $A+I$ is positive semidefinite. Therefore, $A+I=BB^T$ for some matrix $B$. Because the diagonal entries of $A+I$ are all $1$, each column of $B$ is a unit vector. Moreover, since $A+I$ is $0/1$-valued, it follows that if $x$ and $y$ are columns of $B$, then either $x=y$ or $x$ and $y$ are orthogonal. By grouping identical columns of $B$, we see that $A+I$ can be put in block diagonal form, where each block is an all-ones matrix. It follows that $H$ is also a disjoint union of cliques. Finally, it is easy to see that two graphs which are both the disjoint union of cliques have the same spectra if and only if they are isomorphic.

Yes, the cocktail party graphs and $K_{n,n,n}$ are determined by the spectra of their adjacency matrix. See for example, Proposition 6 of the paper Which graphs are determined by their spectrum? by van Dam and Haemers. Proposition 6 shows that the disjoint union of any collection of cliques is DS. You also need to use the fact that if $G$ is regular, than a graph is DS with respect to the adjacency matrix if and only if the complement of $G$ is DS with respect to the adjacency matrix. Since the cocktail party graphs and $K_{n,n,n}$ are both regular and the complement of a disjoint union of cliques, the result follows.

Since the paper appears to be behind a paywall, I will include a proof of Proposition 6 here.

Every graph which is the disjoint union of cliques is determined by the spectra of its adjacency matrix.

Proof. Let $G=K_{n_1} \sqcup \dots \sqcup K_{n_k}$ where $n_1 + \dots n_k=n$. The spectra of $G$ is $n_1-1, \dots, n_k-1, -1, \dots, -1$, where $-1$ occurs $n-k$ times. Let $H$ be a graph with the same spectra and $A$ be the adjacency matrix of $H$. Since all eigenvalues of $A+I$ are nonnegative, $A+I$ is positive semidefinite. Therefore, $A+I=BB^T$ for some matrix $B$. Because the diagonal entries of $A+I$ are all $1$, each column of $B$ is a unit vector. Moreover, since $A+I$ is $0/1$-valued, it follows that if $x$ and $y$ are columns of $B$, then either $x=y$ or $x$ and $y$ are orthogonal. By grouping identical columns of $B$, we see that $A+I$ can be put in block diagonal form, where each block is an all-ones matrix. It follows that $H$ is also a disjoint union of cliques. Finally, it is easy to see that two graphs which are both the disjoint union of cliques have the same spectra if and only if they are isomorphic.

Yes, the cocktail party graphs and $K_{n,n,n}$ are determined by the spectra of their adjacency matrix. See for example, Proposition 6 of the paper Which graphs are determined by their spectrum? by van Dam and Haemers. Proposition 6 shows that the disjoint union of any collection of cliques is DS. You also need to use the fact that if $G$ is regular, than a graph is DS with respect to the adjacency matrix if and only if the complement of $G$ is DS with respect to the adjacency matrix. Since the cocktail party graphs and $K_{n,n,n}$ are both regular and the complement of a disjoint union of cliques, the result follows.

Since the paper appears to be behind a paywall, I will include a proof of Proposition 6 here.

Every graph which is the disjoint union of cliques is determined by the spectra of its adjacency matrix.

Proof. Let $G=K_{n_1} \sqcup \dots \sqcup K_{n_k}$ where $n_1 + \dots +n_k=n$. The spectra of $G$ is $n_1-1, \dots, n_k-1, -1, \dots, -1$, where $-1$ occurs $n-k$ times. Let $H$ be a graph with the same spectra and $A$ be the adjacency matrix of $H$. Since all eigenvalues of $A+I$ are nonnegative, $A+I$ is positive semidefinite. Therefore, $A+I=BB^T$ for some matrix $B$. Because the diagonal entries of $A+I$ are all $1$, each column of $B$ is a unit vector. Moreover, since $A+I$ is $0/1$-valued, it follows that if $x$ and $y$ are columns of $B$, then either $x=y$ or $x$ and $y$ are orthogonal. By grouping identical columns of $B$, we see that $A+I$ can be put in block diagonal form, where each block is an all-ones matrix. It follows that $H$ is also a disjoint union of cliques. Finally, it is easy to see that two graphs which are both the disjoint union of cliques have the same spectra if and only if they are isomorphic.

added 1106 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, the cocktail party graphs and $K_{n,n,n}$ are determined by the spectra of their adjacency matrix. See for example, Proposition 6 of the paper Which graphs are determined by their spectrum? by van Dam and Haemers. Proposition 6 shows that the disjoint union of any collection of complete graphscliques is DS. You also need to use the fact that if $G$ is regular, than a graph is DS with respect to the adjacency matrix if and only if the complement of $G$ is DS with respect to the adjacency matrix. Since the cocktail party graphs and $K_{n,n,n}$ are both regular and the complement of a disjoint union of cliques, the result follows.

Since the paper appears to be behind a paywall, I will include a proof of Proposition 6 here.

Every graph which is the disjoint union of cliques is determined by the spectra of its adjacency matrix.

Proof. Let $G=K_{n_1} \sqcup \dots \sqcup K_{n_k}$ where $n_1 + \dots n_k=n$. The spectra of $G$ is $n_1-1, \dots, n_k-1, -1, \dots, -1$, where $-1$ occurs $n-k$ times. Let $H$ be a graph with the same spectra and $A$ be the adjacency matrix of $H$. Since all eigenvalues of $A+I$ are nonnegative, $A+I$ is positive semidefinite. Therefore, $A+I=BB^T$ for some matrix $B$. Because the diagonal entries of $A+I$ are all $1$, each column of $B$ is a unit vector. Moreover, since $A+I$ is $0/1$-valued, it follows that if $x$ and $y$ are columns of $B$, then either $x=y$ or $x$ and $y$ are orthogonal. By grouping identical columns of $B$, we see that $A+I$ can be put in block diagonal form, where each block is an all-ones matrix. It follows that $H$ is also a disjoint union of cliques. Finally, it is easy to see that two graphs which are both the disjoint union of cliques have the same spectra if and only if they are isomorphic.

Yes, the cocktail party graphs and $K_{n,n,n}$ are determined by the spectra of their adjacency matrix. See for example, Proposition 6 of the paper Which graphs are determined by their spectrum? by van Dam and Haemers. Proposition 6 shows that the disjoint union of any collection of complete graphs is DS. You also need to use the fact that if $G$ is regular, than a graph is DS with respect to the adjacency matrix if and only if the complement of $G$ is DS with respect to the adjacency matrix. Since the cocktail party graphs and $K_{n,n,n}$ are both regular and the complement of a disjoint union of cliques, the result follows.

Yes, the cocktail party graphs and $K_{n,n,n}$ are determined by the spectra of their adjacency matrix. See for example, Proposition 6 of the paper Which graphs are determined by their spectrum? by van Dam and Haemers. Proposition 6 shows that the disjoint union of any collection of cliques is DS. You also need to use the fact that if $G$ is regular, than a graph is DS with respect to the adjacency matrix if and only if the complement of $G$ is DS with respect to the adjacency matrix. Since the cocktail party graphs and $K_{n,n,n}$ are both regular and the complement of a disjoint union of cliques, the result follows.

Since the paper appears to be behind a paywall, I will include a proof of Proposition 6 here.

Every graph which is the disjoint union of cliques is determined by the spectra of its adjacency matrix.

Proof. Let $G=K_{n_1} \sqcup \dots \sqcup K_{n_k}$ where $n_1 + \dots n_k=n$. The spectra of $G$ is $n_1-1, \dots, n_k-1, -1, \dots, -1$, where $-1$ occurs $n-k$ times. Let $H$ be a graph with the same spectra and $A$ be the adjacency matrix of $H$. Since all eigenvalues of $A+I$ are nonnegative, $A+I$ is positive semidefinite. Therefore, $A+I=BB^T$ for some matrix $B$. Because the diagonal entries of $A+I$ are all $1$, each column of $B$ is a unit vector. Moreover, since $A+I$ is $0/1$-valued, it follows that if $x$ and $y$ are columns of $B$, then either $x=y$ or $x$ and $y$ are orthogonal. By grouping identical columns of $B$, we see that $A+I$ can be put in block diagonal form, where each block is an all-ones matrix. It follows that $H$ is also a disjoint union of cliques. Finally, it is easy to see that two graphs which are both the disjoint union of cliques have the same spectra if and only if they are isomorphic.

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

Yes, the cocktail party graphs and $K_{n,n,n}$ are determined by the spectra of their adjacency matrix. See for example, Proposition 6 of the paper Which graphs are determined by their spectrum? by van Dam and Haemers. Proposition 6 shows that the disjoint union of any collection of complete graphs is DS. You also need to use the fact that if $G$ is regular, than a graph is DS with respect to the adjacency matrix if and only if the complement of $G$ is DS with respect to the adjacency matrix. Since the cocktail party graphs and $K_{n,n,n}$ are both regular and the complement of a disjoint union of cliques, the result follows.