3
$\begingroup$

Let's define a coprime graph as a simple graph (undirected graph without any self-loops or multiple-edges) in which for all edges $(𝑢, 𝑣)$, the property $\gcd(\mathrm{degree}_u, \mathrm{degree}_v) = 1$ is true (i.e., degrees of vertices $𝑢$ and $𝑣$ are coprime).

I conjecture that, such a graph with maximum number of edges (is always) can always be obtained as a $k$-partite complete graph.

It has been a while that I have investigated this problem and even proposed an optimization task on that. You can also read the solution.

I would like to know if anyone has some proof or related work?

Improve this question
$\endgroup$
3
  • $\begingroup$ Ten minutes with SageMath shows me that your claim is not true for 7 vertex graphs, because while $K_{3,4}$ has $12$ edges (which is the maximum), there are other coprime graphs with the same number of edges. One example is obtained by taking $K_{2,5}$, then adding 2 incident edges to the set of size $5$. But for $8$ and $9$ vertices, there is a unique winner, namely $K_{1,3,4}$ and $K_{2,3,4}$. $\endgroup$
    – Gordon Royle
    Commented Jan 27, 2022 at 0:15
  • $\begingroup$ It is easy to construct connected infinite graphs with bounded degrees and your property. Maximality of the number of edges makes thus no sense! $\endgroup$
    – Roland Bacher
    Commented Jan 27, 2022 at 8:52
  • $\begingroup$ Sorry, I actually wrote the conjecture incorrectly. It should be "such a graph with maximum number of edges can always be obtained as a $k$-partite complete graph". That means there can be some other graphs with the same number of edges as well. $\endgroup$
    – Rashad Mammadov
    Commented Jan 27, 2022 at 11:19

1 Answer 1

Reset to default
5
$\begingroup$

OK, I can now confirm that even your modified conjecture is false, although the first counterexample has $13$ vertices.

First we need to know which complete $k$-partite graphs on $13$ vertices are coprime and how many edges they have. Both of these things can be determined directly from the sizes of the partite-sets. So for each partition of $13$ with parts $p_1,p_2,\ldots,p_k$ we need to have $n-p_i$ coprime to $n-p_j$ for all $i < j$. For each such partition the number of edges of the corresponding complete $k$-partite graph is $\sum_{i<j}p_ip_j$

In this case, the winner is $K_{3,4,6}$ which has 12+18+24 = 54 edges.

However, here is a nice $13$-vertex graph that is coprime but has $56$ edges.

0 [5, 6, 7, 9, 10, 11, 12] 7
1 [5, 6, 7, 9, 10, 11, 12] 7
2 [5, 6, 8, 9, 10, 11, 12] 7
3 [5, 7, 8, 9, 10, 11, 12] 7
4 [6, 7, 8, 9, 10, 11, 12] 7
5 [0, 1, 2, 3, 8, 9, 10, 11, 12] 9
6 [0, 1, 2, 4, 8, 9, 10, 11, 12] 9
7 [0, 1, 3, 4, 8, 9, 10, 11, 12] 9
8 [2, 3, 4, 5, 6, 7, 11, 12] 8
9 [0, 1, 2, 3, 4, 5, 6, 7, 11, 12] 10
10 [0, 1, 2, 3, 4, 5, 6, 7, 11, 12] 10
11 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 11
12 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 11

Each line contains a vertex name (from $0$-$12$), then a list a neighbours of that vertex, then the degree of that vertex.

The vertices of each fixed degree must be independent sets, and it is easy to check that $\{0,1,2,3,4\}$, $\{5,6,7\}$, $\{9,10\}$ and $\{11,12\}$ are indeed independent.

Any edge involving a vertex of degree $7$, $9$ and $11$ automatically has ends of coprime degree because $7$, $9$ and $11$ are coprime to every other degree. So it is only an edge connecting a vertex of degree $8$ to one of degree $10$ that can prevent this graph from being coprime. And no such edge exists.

You can put this directly into SageMath to construct the graph.

x = Graph("L?BvUo~~v}^~~}")
Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .