FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
No date set
Local EPT graphs on bounded degree trees
María Pía Mazzoleni
Universidad Nacional de La Plata, CONICET, Argentina - pia@mate.unlp.edu.ar
A graph G is called an EPT graph if it is the edge intersection graph of a family of paths in a tree. An EPT representation of G is a pair $\langle \mathcal{P},T \rangle$ where $\mathcal{P}$ is a family $(P_v)_{v\in V(G)}$ of subpaths of the host tree T satisfying that two vertices v and v' of G are adjacent if and only if $P_v$ and $P_{v'}$ have at least two vertices (one edge) in common. When the maximum degree of the host tree T is at most h, the EPT representation of G is called an (h,2,2)-representation of G. The class of graphs which admit an (h,2,2)-representation is denoted by [h,2,2].
Notice that the class of EPT graphs is the union of the classes [h,2,2] for $h\geq 2$. It was proved that the recognition of EPT graphs is an NP-complete problem.
The EPT graphs are used in network applications, where the problem of scheduling undirected calls in a tree network is equivalent to the problem of coloring an EPT graph.
In this paper, we examine the local structure of paths passing through a given vertex of a host tree which has maximum degree h, and show these locally EPT graphs are equivalent to the line graphs of certain graphs.
Definition: Let $\langle \mathcal{P},T \rangle$ be an EPT representation of a graph G. A pie of size n is a star subgraph of T with central vertex q and neighbors $q_1$,...,$q_{n}$ such that each "slice" $q_i\,q\,q_{i+1}$ for $1 \leq i \leq n$ is contained in a different member of $\mathcal{P}$; addition is assumed to be module n.
Let $\langle \mathcal{P},T \rangle$ be an EPT representation of a graph G. It was proved that if G contains a chordless cycle of length $n\geq 4$, then $\langle \mathcal{P},T \rangle$ contains a pie of size n.
Definition: We say that $\langle \mathcal{P},T \rangle$ is a local EPT representation of G if it is an EPT representation where all the paths of $\mathcal{P}$ share a common vertex of T.
We call G a local EPT graph if it has a local EPT representation.
Let $h\geq 5$, we say that G belongs to the class [h,2,2] local if and only if G has a local EPT representation in a host tree T with maximum degree h.
In this work, we characterize the graphs which belongs to the class [h,2,2] local.
Definition: Let G be a connected graph. We say that $v\in V(G)$ is a cut vertex of G if G-v has at least two connected components.
Theorem 1: Let $h\geq 5$. If $G\in [h,2,2]$ local and $G\notin [h-1,2,2]$ then G has no cut vertices.
We show that this special subclass of EPT graphs is equivalent to the class of line graphs of certain graphs which have certain properties.
Definition: Let H be a graph, the line graph of H, noted by L(H), has vertices corresponding to the edges of H with two vertices adjacent in L(H) if their corresponding edges of H share an endpoint.
Definition: We say that two vertices u,v of G are adjacent dominated vertices if $uv\in E(G)$ and $N_G(u)\subseteq N_G(v)$ or $N_G(v)\subseteq N_G(u)$.
Theorem 2: Let $h\geq 5$. $G\in [h,2,2]$ local, $G\notin [h-1,2,2]$ and G without adjacent dominated vertices if and only if G=L(H) with H a graph such that:
(i) |V(H)|=h; (ii) H has no vertices of degree 1; (iii) H is simple; (iv) H has no adjacent dominated vertices; (v) H has a cycle $C_n$, with $4 \leq n\leq h$; and every vertex of $H-C_n$ is in some path between two different vertices of $C_n$.
Conjecture: Let $h\geq 5$. If $G\in [h,2,2]$, $G\notin [h-1,2,2]$ but $G-v\in [h-1,2,2]$, for all $v\in V(G)$, then $G\in [h,2,2]$ local.
Joint work with Liliana Alcón (Universidad Nacional de La Plata, Argentina) and Marisa Gutierrez (Universidad Nacional de La Plata, CONICET, Argentina).