Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
Concerning (3), should the $D$'s be there? –  Tony Huynh Oct 1 '10 at 19:41
    
Thank you! Corrected) –  Alexander Oct 1 '10 at 20:01

2 Answers 2

up vote 3 down vote accepted

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.

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

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!

share|improve this answer
    
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$. –  Alexander Oct 1 '10 at 20:32
    
Of course, $G$ and $H$ are not isomorphic. –  Alexander Oct 1 '10 at 20:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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