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?

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

2 Answers 2

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.

$\endgroup$
4
  • $\begingroup$ Please, give me adjacency matrices of these trees. It would do the trick better) $\endgroup$
    – Alexander
    Oct 1, 2010 at 21:41
  • $\begingroup$ Thank you, daniel! Got it. There's no need for adjacency matrices. $\endgroup$
    – Alexander
    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
    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
    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!

$\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
    Oct 1, 2010 at 20:32
  • $\begingroup$ Of course, $G$ and $H$ are not isomorphic. $\endgroup$
    – Alexander
    Oct 1, 2010 at 20:39

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.