Graphoidal graphs and graphoidal digraphs: a generalization of line graphs

Abstract

A graphoidal cover of a graph G is a collection ψ of paths (not necessarily open) in G such that each path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ, and every edge of G is in exactly one path in Let denote the intersection graph of A graph H is called a graphoidal graph if there exists a graph G and a graphoidal cover ψ of G such that H is isomorphic to Graphoidal covers of digraphs can be similarly defined. In this article, we present a survey of known results on graphoidal graphs. We also introduce the concept of graphoidal digraphs, provide some results, and discuss several problems for further investigation.

Keywords

• graphoidal cover
• line graph
• line digraph
• graphoidal graph
• graphoidal digraph