2
$\begingroup$

Constructing trees with the same degree sequences I've got this problem.

Let $G$, $H$ be the trees (simple graphs) with the same degree sequences. Is it true that there always be vertices $q\in V(G)$ and $q′\in V(H)$ such that $(q,p)\in E(G)$ and $(q′,p′)\in E(H)$ for some endvertices $p\in V(G)$ and $p\in V(H)$, and $d(q)=d(q′)$?

$d(q)$ - degree of the vertex $q$.

I haven't found counterexample for trees up to $8$ vertices, and it's seems impossible to me.

Have you references for some results concerned with trees with the same degree sequences?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Concerning (3), should the $D$'s be there? $\endgroup$
    – Tony Huynh
    Commented Oct 1, 2010 at 19:41

2 Answers 2

Reset to default
3
$\begingroup$

Consider two trees $G$ and $H$ with 14 vertices. Both will have degree sequence $(2,0,6,6)$ i.e. having two vertices of degree 4. $G$ will have the two 4-vertices connected to 3 leaves each and with a 6 vertex long chain between them. $H$ will have the two 4-vertices connected with a single edge. In addition, each will have three 2 vertex long chains connected to them (one 2-vertex connected to a leaf).

Finally, each leaf of $G$ is connected to a 4 vertex and each leaf of $H$ is connected to a 2 vertex.

A picture would do the trick better.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Please, give me adjacency matrices of these trees. It would do the trick better) $\endgroup$
    – Alexander
    Commented Oct 1, 2010 at 21:41
  • $\begingroup$ Thank you, daniel! Got it. There's no need for adjacency matrices. $\endgroup$
    – Alexander
    Commented Oct 1, 2010 at 22:08
  • 2
    $\begingroup$ Of course, there is a simpler example with 10 vertices. Perhaps I can even draw: =>-<= and >-----< . $\endgroup$
    – daniel
    Commented Oct 1, 2010 at 22:22
  • $\begingroup$ Thank you, Daniel! You help me. My english not so good to say HOW MUCH you help me, indeed) $\endgroup$
    – Alexander
    Commented Oct 2, 2010 at 9:05
4
$\begingroup$

Let $G$ be the Dynkin diagram of $A_5$ and $H$ be the Dynkin diagram of $D_5$. Then $G$ can be extended to the Dynkin diagram of $E_6$, while $H$ can be extended to the Dynkin diagram of $D_6$. These examples satisfy your conditions. I would draw them, as they are not much more elaborate than paths, but my tex skills are not that good!

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for the answer, damiano. I know this already) I just have formulated the problem quite incorrectly. Sorry. Indeed, the problem is formulating as follows. Let $G$ and $H$ be the trees with the same degree sequences. Is it true that there always be vertices $q\in V(G)$ and $q′\in V(H)$ such that $(q,p)\in E(G)$ and $(q′,p′)\in E(H)$ for some endvertices $p\in V(G)$ and $p\in V(H)$, and $d(q)=d(q′)$? $d(q)$ - degree of the vertex $q$. $\endgroup$
    – Alexander
    Commented Oct 1, 2010 at 20:32
  • $\begingroup$ Of course, $G$ and $H$ are not isomorphic. $\endgroup$
    – Alexander
    Commented Oct 1, 2010 at 20:39

You must log in to answer this question.

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