Can a directed graph be completed to a directed line graph? If possible, how many arcs must be added? In this paper we address the above questions characterizing partial directed line (PDL) graphs, i.e., partial subgraph of directed line graphs. We show that for such class of graphs a forbidden configuration criterion and a Krausz's like theorem are equivalent characterizations. Furthermore, the latter leads to a recognition algorithm that requires O(m) worst case time, where m is the number of arcs in the graph. Given a partial line digraph, our characterization allows us to find a minimum completion to a directed line graph within the same time bound. The class of PDL graphs properly contains the class of directed line graphs, characterized in [J. Blazewicz, A. Hertz, D. Kobler, D. de Werra, On some properties of DNA graphs, Discrete Appl. Math. 98(1-2) (1999) 1-19], hence our results generalize those already known for directed line graphs. In the undirected case, we show that finding a minimum line graph edge completion is NP-hard. while the problem of deciding whether or not an undirected graph is a partial graph of a simple line graph is trivial. (C) 2007 Elsevier B.V. All rights reserved.
A characterization of partial directed line graphs / Nicola, Apollonio; Franciosa, Paolo Giulio. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - STAMPA. - 307:21(2007), pp. 2598-2614. [10.1016/j.disc.2007.01.009]
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||A characterization of partial directed line graphs|
|Data di pubblicazione:||2007|
|Citazione:||A characterization of partial directed line graphs / Nicola, Apollonio; Franciosa, Paolo Giulio. - In: DISCRETE MATHEMATICS. - ISSN 0012-365X. - STAMPA. - 307:21(2007), pp. 2598-2614. [10.1016/j.disc.2007.01.009]|
|Appartiene alla tipologia:||01a Articolo in rivista|