3
$\begingroup$

Question 1. Let $\Gamma=(V,E)$ be a connected graph with $n$ vertices, all of degree $d\geq 4$. Assume every vertex has $d$ distinct neighbors. (We can think of $d$ as being much smaller than $n$, but not necessarily bounded.)

As is customary, for a set of vertices $W\subset V$, we define the boundary $\partial W$ to be the set of vertices not in $W$ that have at least one neighbor in $W$. Call a set $W\subset V$ connected if the corresponding subgraph $\Gamma|_{W}$ of $\Gamma$ is connected. Write $|S|$ for the number of elements of a set $S$.

What sort of lower bound can we give on $\max_{\text{$W\subset V$ connected}} |\partial W|$?

Question 2. What happens if you remove the assumption that all vertices have the same degree, and just require them to have degree between $3$ and $d$, say?

Improve this question
$\endgroup$
2
  • $\begingroup$ Are you at least assuming that $\Gamma$ is connected ? Otherwise the optimal lower bound seems to be $d$ (consider a disjoint union of complete graphs of degree $d$)... $\endgroup$
    – Mikael de la Salle
    Jun 4, 2020 at 9:58
  • $\begingroup$ Yes, I was assuming that - thanks. I've added the assumption. $\endgroup$
    – H A Helfgott
    Jun 4, 2020 at 10:02

2 Answers 2

Reset to default
6
$\begingroup$

If all degrees are at least 3, there exists a spanning tree with at least $n/4+2$ leaves (D. J. Kleitman and D. B. West, Spanning trees with many leaves, SIAM J. Disc. Math. 4(1991), 99-106), the сomplement of these leaves gives you a connected set with boundary of size at least $n/4+2$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Nice! As the paper says, the result is a little bit older. $\endgroup$
    – H A Helfgott
    Jun 4, 2020 at 12:17
  • $\begingroup$ For better visibility: Kleitman and West prove that if the minimum degree of a graph is $d\geq 4$, then there is a spanning tree with at least $2n/5 + 8/5$ leaves. $\endgroup$
    – Harry Richman
    May 12, 2022 at 21:09
1
$\begingroup$

The first question asked is the just the maximum leaf number of the graph. The problem of finding it is in general NP-Hard. For references, I think a good one is this, which is algorithmic. A recent paper is here. Note that the maximum leaf number is $n-d(G)$ where $d(G)$ is the connected domination number of the graph $G$.

By the way, your notation seems confusing. Not all vertices can have $d$ distinct neighbors if the graph is $d$-regular. The adjacent vertices always have one common neighbor, isnt it?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Can you send me your actual name, so that I can add you to the acknowledgements? $\endgroup$
    – H A Helfgott
    Jul 30, 2020 at 16:10
  • $\begingroup$ @HAHelfgott sorry, I didnt get you. Are you trying to acknowledge me in some paper or conference or something similar? $\endgroup$
    – vidyarthi
    Jul 30, 2020 at 17:44
  • $\begingroup$ Paper, acknowledgements section. $\endgroup$
    – H A Helfgott
    Jul 30, 2020 at 20:14
  • $\begingroup$ F. Petrov is already there :). $\endgroup$
    – H A Helfgott
    Jul 30, 2020 at 20:15
  • 1
    $\begingroup$ @HAHelfgott I dont think I did something new in this answer. Anyways, you can cite me as is, by my username. You can give me an upvote for this answer as the acknowledgement !! When I would try to write a number theory paper, I would try to collaborate with you. Then, I would let you know my full name!! I think you would be open to email discussions? $\endgroup$
    – vidyarthi
    Jul 30, 2020 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.