The biplanar tree graph
- PDF / 812,646 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 84 Downloads / 183 Views
ORIGINAL ARTICLE
The biplanar tree graph Ana Paulina Figueroa1,2
•
Julia´n Fresa´n-Figueroa1,2
Received: 7 August 2019 / Accepted: 17 March 2020 Sociedad Matemática Mexicana 2020
Abstract The complete twisted graph of order n, denoted by Tn , is a complete simple topological graph with vertices u1 ; u2 ; . . .; un such that two edges ui uj and ui0 uj0 cross if and only if i\i0 \j0 \j or i0 \i\j\j0 . The convex geometric complete graph of order n, denoted by Gn , is a convex geometric graph with vertices v1 ; v2 ; . . .; vn placed counterclockwise, in which every pair of vertices is adjacent. A biplanar tree of order n is a labeled tree with vertex set fv1 ; v2 ; . . .; vn g having the property of being planar when embedded in both Tn and Gn . Given a connected graph G the (combinatorial) tree graph T ðGÞ is the graph whose vertices are the spanning trees of G and two trees P and Q are adjacent in T ðGÞ if there are edges e 2 P and f 2 Q such that Q ¼ P e þ f . For all positive integers n, we denote by T ðnÞ the graph T ðKn Þ. The biplanar tree graph, BðnÞ, is the subgraph of T ðnÞ induced by the biplanar trees of order n. In this paper we give a characterization of the biplanar trees and we study the structure, the radius and the diameter of the biplanar tree graph.
Mathematics Subject Classification 05C10 05C05 05C76 05C40
Partial support of Asociacio´n de Cultura Mexicana A.C and CONACyT, Me´xico Projects A1-S-12891 and 47510664. & Ana Paulina Figueroa [email protected] Julia´n Fresa´n-Figueroa [email protected] 1
Departamento Acade´mico de Matema´ticas, ITAM, Mexico City, Mexico
2
Departamento de Matema´ticas Aplicadas y Sistemas, UAM-C, Mexico City, Mexico
123
A. P. Figueroa et al.
1 Introduction Let P be a set of points in the plane. A simple topological graph with vertex set P is a drawing of a simple graph whose vertices are points in P and the edges are simple continuous arcs such that any two arcs have at most one point in common (either a common endpoint or a crossing) and such that the only vertices in each arc are its endpoints. A geometric graph is a topological graph in which all edges are straightline segments. A geometric graph whose vertices are in convex position is called a convex geometric graph. The complete twisted graph of order n, denoted by Tn , is a complete simple topological graph with vertices u1 ; u2 ; . . .; un such that two edges ui uj and ui0 uj0 cross if and only if i\i0 \j0 \j or i0 \i\j\j0 . The convex geometric complete graph of order n, denoted by Gn , is a convex geometric graph with vertices v1 ; v2 ; . . .; vn placed counterclockwise, in which every pair of vertices is adjacent. 0 0 Observe that two edges vi vj ði\jÞ and vi0 vj0 ði \j Þ cross each other in Gn if and 0
0
0
0
only if i\i \j\j or i \i\j \j: Two simple topological graphs G and H are weakly isomorphic if there exists an isomorphism between G and H such that two edges of H cross if and only if their corresponding edges of G cross. Observe that Gn is weakly isomorphic to a drawin
Data Loading...
