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
    Commented Jun 4, 2020 at 9:58
  • $\begingroup$ Yes, I was assuming that - thanks. I've added the assumption. $\endgroup$
    – H A Helfgott
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented Jul 30, 2020 at 17:44
  • $\begingroup$ Paper, acknowledgements section. $\endgroup$
    – H A Helfgott
    Commented Jul 30, 2020 at 20:14
  • $\begingroup$ F. Petrov is already there :). $\endgroup$
    – H A Helfgott
    Commented 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
    Commented Jul 30, 2020 at 20:25

You must log in to answer this question.

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