Graphs of edge-intersecting non-splitting paths in a tree: Towards hole representations (extended abstract)
39th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2013, Lübeck, Almanya, 19 - 21 Haziran 2013, cilt.8165 LNCS, ss.115-126, (Tam Metin Bildiri)
- Yayın Türü: Bildiri / Tam Metin Bildiri
- Cilt numarası: 8165 LNCS
- Doi Numarası: 10.1007/978-3-642-45043-3_11
- Basıldığı Şehir: Lübeck
- Basıldığı Ülke: Almanya
- Sayfa Sayıları: ss.115-126
- Boğaziçi Üniversitesi Adresli: Evet
Özet
Given a tree and a set P of non-trivial simple paths on it, Vpt(P) is the VPT graph (i.e. the vertex intersection graph) of P, and Ept(P) is the EPT graph (i.e. the edge intersection graph) of the paths P of the tree T. These graphs have been extensively studied in the literature. Given two (edge) intersecting paths in a graph, their split vertices is the set of vertices having degree at least 3 in their union. A pair of (edge) intersecting paths is termed non-splitting if they do not have split vertices (namely if their union is a path). In this work, we define the graph Enpt(P) of edge intersecting non-splitting paths of a tree, termed the ENPT graph, as the (edge) graph having a vertex for each path in P, and an edge between every pair of paths that are both edge-intersecting and non-splitting. A graph G is an ENPT graph if there is a tree T and a set of paths P of T such that G = Ept(P) , and we say that 〈T,P〉 is a representation of G. We show that trees, cycles and complete graphs are ENPT graphs. We characterize the representations of chordless ENPT cycles that satisfy a certain assumption. Unlike chordless EPT cycles which have a unique representation, these representations turn out to be multiple and have a more complex structure. Therefore, in order to give this characterization, we assume the EPT graph induced by the vertices of a chordless ENPT cycle is given, and we provide an algorithm that returns the unique representation of this EPT, ENPT pair of graphs. These representations turn out to have a more complex structure than chordless EPT cycles. © 2013 Springer-Verlag.