Mixing
Is it possible that both a graph and its complement, have small connectivity?
Clash Royale CLAN TAG#URR8PPP
up vote
7
down vote
favorite
Let $G=(V,E)$ be a simple graph with $n$ vertex. The isoperimetric constant of $G$ defined as
$$
i(G) := min_A subset V, fracA
$$
where $partial A$ is the set edges $uv in E$, with $v in A$ and $u in A^c$.
Is there a graph $G$ such that $$i(G) + i(G^c) < frac 12$$
where $G^c$ denote the complement of $G$?
co.combinatorics graph-theory discrete-geometry
asked 4 hours ago
Mahdi
1,0782722
add a comment |Â
up vote
7
down vote
favorite
Let $G=(V,E)$ be a simple graph with $n$ vertex. The isoperimetric constant of $G$ defined as
$$
i(G) := min_A subset V, fracA
$$
where $partial A$ is the set edges $uv in E$, with $v in A$ and $u in A^c$.
Is there a graph $G$ such that $$i(G) + i(G^c) < frac 12$$
where $G^c$ denote the complement of $G$?
co.combinatorics graph-theory discrete-geometry
asked 4 hours ago
Mahdi
1,0782722
Would you state the definition of $partial A$?
– Wlod AA
3 hours ago
1
@WlodAA: I edited the question.
– Mahdi
3 hours ago
Thank you. Seems to me interesting. I'll try to look at it more.
– Wlod AA
2 hours ago
add a comment |Â
up vote
7
down vote
favorite
up vote
7
down vote
favorite
Let $G=(V,E)$ be a simple graph with $n$ vertex. The isoperimetric constant of $G$ defined as
$$
i(G) := min_A subset V, fracA
$$
where $partial A$ is the set edges $uv in E$, with $v in A$ and $u in A^c$.
Is there a graph $G$ such that $$i(G) + i(G^c) < frac 12$$
where $G^c$ denote the complement of $G$?
co.combinatorics graph-theory discrete-geometry
asked 4 hours ago
Mahdi
1,0782722
Let $G=(V,E)$ be a simple graph with $n$ vertex. The isoperimetric constant of $G$ defined as
$$
i(G) := min_A subset V, fracA
$$
where $partial A$ is the set edges $uv in E$, with $v in A$ and $u in A^c$.
Is there a graph $G$ such that $$i(G) + i(G^c) < frac 12$$
where $G^c$ denote the complement of $G$?
co.combinatorics graph-theory discrete-geometry
co.combinatorics graph-theory discrete-geometry
asked 4 hours ago
Mahdi
1,0782722
asked 4 hours ago
Mahdi
1,0782722
edited 3 hours ago
asked 4 hours ago
Mahdi
1,0782722
asked 4 hours ago
Mahdi
1,0782722
asked 4 hours ago
Mahdi
1,0782722
1,0782722
Would you state the definition of $partial A$?
– Wlod AA
3 hours ago
1
@WlodAA: I edited the question.
– Mahdi
3 hours ago
Thank you. Seems to me interesting. I'll try to look at it more.
– Wlod AA
2 hours ago
add a comment |Â
Would you state the definition of $partial A$?
– Wlod AA
3 hours ago
1
@WlodAA: I edited the question.
– Mahdi
3 hours ago
Thank you. Seems to me interesting. I'll try to look at it more.
– Wlod AA
2 hours ago
Would you state the definition of $partial A$?
– Wlod AA
3 hours ago
Would you state the definition of $partial A$?
– Wlod AA
3 hours ago
1
1
@WlodAA: I edited the question.
– Mahdi
3 hours ago
@WlodAA: I edited the question.
– Mahdi
3 hours ago
Thank you. Seems to me interesting. I'll try to look at it more.
– Wlod AA
2 hours ago
Thank you. Seems to me interesting. I'll try to look at it more.
– Wlod AA
2 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Since for comment is long, I write the contribution here:
Let $A$ and $L$ be the adjacency matrix and Laplacian matrix of the graph $G$, respectively. Also, suppose $mu_2$ denotes the second smallest eigenvalue of $L$ and $lambda_2$ be the second largest eigenvalue of $A$. It is proved that $i(G)geq fracmu_22$ (see Theorem 4.1 of enter link description here). So, we have $$i(G)+i(G^c)geq fracmu_2(G)+mu_2(G^c)2$$.
So, if we have an example for your question, we must find graph $G$ such that $mu_2(G)+mu_2(G^c)<1$. By some spectral graph theory, it can be seen that finding such a graph is a difficult problem. But, finding the spectrum of a graph is much easier than finding its isoperimetric number.
Also, it can be shown that this problem is related to the classification of the graphs based on their second largest eigenvalue of the adjacency matrix. Actually, if we can find a suitable graph such that:
$$lambda_2(G)+lambda_2(G^c)leq delta(G)-Delta(G)+n-2$$,
Then we find an example; where $delta(G)$ and $Delta(G)$ shows the minimum and maximum degree of the graph $G$ with $n$ vertices.
$textbfAdded later:$ By the relation $mu_2(G)+mu_2(G^c)<1$ and some random graph testing, it seems that such graphs are so rare. There is not any example of such graph up to 6 vertices. Also, it seems that we can prove $mu_2(G)+mu_2(G^c)geq 1$, which means there is not such an example.
answered 1 hour ago
Shahrooz Janbaz
2,5641822
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Since for comment is long, I write the contribution here:
Let $A$ and $L$ be the adjacency matrix and Laplacian matrix of the graph $G$, respectively. Also, suppose $mu_2$ denotes the second smallest eigenvalue of $L$ and $lambda_2$ be the second largest eigenvalue of $A$. It is proved that $i(G)geq fracmu_22$ (see Theorem 4.1 of enter link description here). So, we have $$i(G)+i(G^c)geq fracmu_2(G)+mu_2(G^c)2$$.
So, if we have an example for your question, we must find graph $G$ such that $mu_2(G)+mu_2(G^c)<1$. By some spectral graph theory, it can be seen that finding such a graph is a difficult problem. But, finding the spectrum of a graph is much easier than finding its isoperimetric number.
Also, it can be shown that this problem is related to the classification of the graphs based on their second largest eigenvalue of the adjacency matrix. Actually, if we can find a suitable graph such that:
$$lambda_2(G)+lambda_2(G^c)leq delta(G)-Delta(G)+n-2$$,
Then we find an example; where $delta(G)$ and $Delta(G)$ shows the minimum and maximum degree of the graph $G$ with $n$ vertices.
$textbfAdded later:$ By the relation $mu_2(G)+mu_2(G^c)<1$ and some random graph testing, it seems that such graphs are so rare. There is not any example of such graph up to 6 vertices. Also, it seems that we can prove $mu_2(G)+mu_2(G^c)geq 1$, which means there is not such an example.
answered 1 hour ago
Shahrooz Janbaz
2,5641822
add a comment |Â
up vote
2
down vote
Since for comment is long, I write the contribution here:
Let $A$ and $L$ be the adjacency matrix and Laplacian matrix of the graph $G$, respectively. Also, suppose $mu_2$ denotes the second smallest eigenvalue of $L$ and $lambda_2$ be the second largest eigenvalue of $A$. It is proved that $i(G)geq fracmu_22$ (see Theorem 4.1 of enter link description here). So, we have $$i(G)+i(G^c)geq fracmu_2(G)+mu_2(G^c)2$$.
So, if we have an example for your question, we must find graph $G$ such that $mu_2(G)+mu_2(G^c)<1$. By some spectral graph theory, it can be seen that finding such a graph is a difficult problem. But, finding the spectrum of a graph is much easier than finding its isoperimetric number.
Also, it can be shown that this problem is related to the classification of the graphs based on their second largest eigenvalue of the adjacency matrix. Actually, if we can find a suitable graph such that:
$$lambda_2(G)+lambda_2(G^c)leq delta(G)-Delta(G)+n-2$$,
Then we find an example; where $delta(G)$ and $Delta(G)$ shows the minimum and maximum degree of the graph $G$ with $n$ vertices.
$textbfAdded later:$ By the relation $mu_2(G)+mu_2(G^c)<1$ and some random graph testing, it seems that such graphs are so rare. There is not any example of such graph up to 6 vertices. Also, it seems that we can prove $mu_2(G)+mu_2(G^c)geq 1$, which means there is not such an example.
answered 1 hour ago
Shahrooz Janbaz
2,5641822
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Since for comment is long, I write the contribution here:
Let $A$ and $L$ be the adjacency matrix and Laplacian matrix of the graph $G$, respectively. Also, suppose $mu_2$ denotes the second smallest eigenvalue of $L$ and $lambda_2$ be the second largest eigenvalue of $A$. It is proved that $i(G)geq fracmu_22$ (see Theorem 4.1 of enter link description here). So, we have $$i(G)+i(G^c)geq fracmu_2(G)+mu_2(G^c)2$$.
So, if we have an example for your question, we must find graph $G$ such that $mu_2(G)+mu_2(G^c)<1$. By some spectral graph theory, it can be seen that finding such a graph is a difficult problem. But, finding the spectrum of a graph is much easier than finding its isoperimetric number.
Also, it can be shown that this problem is related to the classification of the graphs based on their second largest eigenvalue of the adjacency matrix. Actually, if we can find a suitable graph such that:
$$lambda_2(G)+lambda_2(G^c)leq delta(G)-Delta(G)+n-2$$,
Then we find an example; where $delta(G)$ and $Delta(G)$ shows the minimum and maximum degree of the graph $G$ with $n$ vertices.
$textbfAdded later:$ By the relation $mu_2(G)+mu_2(G^c)<1$ and some random graph testing, it seems that such graphs are so rare. There is not any example of such graph up to 6 vertices. Also, it seems that we can prove $mu_2(G)+mu_2(G^c)geq 1$, which means there is not such an example.
answered 1 hour ago
Shahrooz Janbaz
2,5641822
Since for comment is long, I write the contribution here:
Let $A$ and $L$ be the adjacency matrix and Laplacian matrix of the graph $G$, respectively. Also, suppose $mu_2$ denotes the second smallest eigenvalue of $L$ and $lambda_2$ be the second largest eigenvalue of $A$. It is proved that $i(G)geq fracmu_22$ (see Theorem 4.1 of enter link description here). So, we have $$i(G)+i(G^c)geq fracmu_2(G)+mu_2(G^c)2$$.
So, if we have an example for your question, we must find graph $G$ such that $mu_2(G)+mu_2(G^c)<1$. By some spectral graph theory, it can be seen that finding such a graph is a difficult problem. But, finding the spectrum of a graph is much easier than finding its isoperimetric number.
Also, it can be shown that this problem is related to the classification of the graphs based on their second largest eigenvalue of the adjacency matrix. Actually, if we can find a suitable graph such that:
$$lambda_2(G)+lambda_2(G^c)leq delta(G)-Delta(G)+n-2$$,
Then we find an example; where $delta(G)$ and $Delta(G)$ shows the minimum and maximum degree of the graph $G$ with $n$ vertices.
$textbfAdded later:$ By the relation $mu_2(G)+mu_2(G^c)<1$ and some random graph testing, it seems that such graphs are so rare. There is not any example of such graph up to 6 vertices. Also, it seems that we can prove $mu_2(G)+mu_2(G^c)geq 1$, which means there is not such an example.
answered 1 hour ago
Shahrooz Janbaz
2,5641822
edited 23 mins ago
answered 1 hour ago
Shahrooz Janbaz
2,5641822
answered 1 hour ago
Shahrooz Janbaz
2,5641822
answered 1 hour ago
Shahrooz Janbaz
2,5641822
2,5641822
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f311862%2fis-it-possible-that-both-a-graph-and-its-complement-have-small-connectivity%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Would you state the definition of $partial A$?
– Wlod AA
3 hours ago
1
@WlodAA: I edited the question.
– Mahdi
3 hours ago
Thank you. Seems to me interesting. I'll try to look at it more.
– Wlod AA
2 hours ago