<p>I'm looking for a binary graph operation $\oplus$ that has the following properties for all undirected graphs $G_1$ and $G_2$.</p>

<ol>
<li>If $d_1$ is the largest number for which $G_1$ has a subgraph of minimum degree $d_1$, and $d_2$ the largest such number for $G_2$, then the largest such number for $G_1 \oplus G_2$ should be $d_1 + d_2$. In other words, $$\max_{H \subseteq G_1} \delta(H) + \max_{H \subseteq G_2} \delta(H) = \max_{H \subseteq G_1 \oplus G_2} \delta(H),$$ where $\delta(H)$ denotes the minimum degree of the subgraph $H$.</li>
<li>$|G_1 \oplus G_2| \in O(|G_1| + |G_2|)$.</li>
<li>$G_1 \oplus G_2$ is computable in logarithmic space.</li>
</ol>

<p>I believe the <a href="https://en.wikipedia.org/wiki/Graph_product" rel="nofollow">Cartesian product</a> for graphs satisfies the first and the third conditions, but the size of the product graph in this case is multiplicative (specifically $O(|G_1| \cdot |G_2|)$), not additive. I will be performing this operation a polynomial number of times, so a multiplicative increase in size is unacceptable.</p>

<p><em>Edit: changed condition 3 to require a logarithmic space computation instead of a polynomial time computation.</em></p>

<p><em>Edit: changed condition 1 to require the maximum minimum degree over all subgraphs should be preserved.</em></p>

CC BY-SA 3.0
2013-06-15T03:56:30.957Z
I obviously did not describe the problem correctly, sorry about that. I have changed condition 1 to require that the maximum over all subgraphs of the minimum degree of the subgraph is preserved.
argentpepper
CC BY-SA 3.0
2013-06-15T11:07:44.193Z
This still allows using a big clique as the sum, as David suggests.  What implicit condition do you have in mind that stops this?
András Salamon
CC BY-SA 3.0
2013-06-11T20:58:52.317Z
Do you need any structure of $G_1$ and $G_2$ to be preserved? Because the obvious answer is: let $a$ be the maximum value such that $G_1$ has a subgraph of minimum degree $a$ (essentially this is the degeneracy of $G_1$ and can be computed in linear time), let $b$ be defined in the same way from $G_2$, and define $G_1\oplus G_2$ to be a clique with $a+b+1$ vertices. Or if you want $G_1$ and $G_2$ to be subgraphs, define $G_1\oplus G_2$ to be the disjoint sum of this clique, $G_1$, and $G_2$.
David Eppstein
CC BY-SA 3.0
2013-06-13T18:46:02.323Z
@DavidEppstein You are of course correct. I made a mistake in describing the conditions necessary for the operation. It turns out that polynomial time is not allowed, only logarithmic space. This way the operation cannot determine whether a graph has a subgraph of minimum degree $a$ (because the High Degree Subgraph problem is $\mathsf{P}$-complete). I will edit the question to reflect this correction.
argentpepper
CC BY-SA 3.0
2013-06-13T21:36:11.823Z
@argentpepper: Changing the complexity in this way does not avoid David's objection.
András Salamon
CC BY-SA 3.0
2013-06-13T22:46:17.530Z
What if $G_1 \oplus G_2$ is simply a clique of size $|G_1| + |G_2|$ ?
Mahdi Cheraghchi
<graph-theory>
Looking for an "additive" binary graph operation that preserves subgraphs of high degree
argentpepper
# Looking for an "additive" binary graph operation that preserves subgraphs of high degree

(Asked by: username_0 on 2013-06-11)

I'm looking for a binary graph operation $\oplus$ that has the following properties for all undirected graphs $G\_1$ and $G\_2$.

1. If $d\_1$ is the largest number for which $G\_1$ has a subgraph of minimum degree $d\_1$, and $d\_2$ the largest such number for $G\_2$, then the largest such number for $G\_1 \oplus G\_2$ should be $d\_1 + d\_2$. In other words, $$\max\_{H \subseteq G\_1} \delta(H) + \max\_{H \subseteq G\_2} \delta(H) = \max\_{H \subseteq G\_1 \oplus G\_2} \delta(H),$$ where $\delta(H)$ denotes the minimum degree of the subgraph $H$.
2. $|G\_1 \oplus G\_2| \in O(|G\_1| + |G\_2|)$.
3. $G\_1 \oplus G\_2$ is computable in logarithmic space.

I believe the [Cartesian product](https://en.wikipedia.org/wiki/Graph_product) for graphs satisfies the first and the third conditions, but the size of the product graph in this case is multiplicative (specifically $O(|G\_1| \cdot |G\_2|)$), not additive. I will be performing this operation a polynomial number of times, so a multiplicative increase in size is unacceptable.

*Edit: changed condition 3 to require a logarithmic space computation instead of a polynomial time computation.*

*Edit: changed condition 1 to require the maximum minimum degree over all subgraphs should be preserved.*

**Tags:** graph-theory
> **Comments:**
> **username_2**: Do you need any structure of $G_1$ and $G_2$ to be preserved? Because the obvious answer is: let $a$ be the maximum value such that $G_1$ has a subgraph of minimum degree $a$ (essentially this is the degeneracy of $G_1$ and can be computed in linear time), let $b$ be defined in the same way from $G_2$, and define $G_1\oplus G_2$ to be a clique with $a+b+1$ vertices. Or if you want $G_1$ and $G_2$ to be subgraphs, define $G_1\oplus G_2$ to be the disjoint sum of this clique, $G_1$, and $G_2$.  
> **username_0**: @DavidEppstein You are of course correct. I made a mistake in describing the conditions necessary for the operation. It turns out that polynomial time is not allowed, only logarithmic space. This way the operation cannot determine whether a graph has a subgraph of minimum degree $a$ (because the High Degree Subgraph problem is $\mathsf{P}$-complete). I will edit the question to reflect this correction.  
> **username_1**: @argentpepper: Changing the complexity in this way does not avoid David's objection.  
> **username_3**: What if $G_1 \oplus G_2$ is simply a clique of size $|G_1| + |G_2|$ ?  
> **username_0**: I obviously did not describe the problem correctly, sorry about that. I have changed condition 1 to require that the maximum over all subgraphs of the minimum degree of the subgraph is preserved.  
> **username_1**: This still allows using a big clique as the sum, as David suggests.  What implicit condition do you have in mind that stops this?  

---

## 0 answers

