Name
Abstract | ||
|---|---|---|
We study the problem of adding edges to a given arbitrary graph so that the resulting graph is a split graph, called a split completion of the input graph. Our purpose is to add an inclusion minimal set of edges to obtain a minimal split completion, which means that no proper subset of the added edges is sufficient to create a split completion. Minimal completions of arbitrary graphs into chordal graphs have been studied previously, and new results have been added continuously. There is an increasing interest in minimal completion problems, and minimal completions of arbitrary graphs into interval graphs have been studied very recently. We extend these previous results to split graphs, and we give a characterization of minimal split completions, along with a linear time algorithm for computing a minimal split completion of an arbitrary input graph. Among our results is a new way of partitioning the vertices of a split graph uniquely into three subsets. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11682462_55 | LATIN |
Keywords | Field | DocType |
minimal completion,inclusion minimal set,split completion,minimal split completion,arbitrary input graph,arbitrary graph,chordal graph,minimal completion problem,split graph,input graph,interval graph | Discrete mathematics,Block graph,Combinatorics,Indifference graph,Modular decomposition,Interval graph,Chordal graph,Cograph,Pathwidth,Mathematics,Split graph | Conference |
Volume | ISSN | ISBN |
3887 | 0302-9743 | 3-540-32755-X |
Citations | PageRank | References |
9 | 0.54 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Pinar Heggernes | 1 | 845 | 72.39 |
| Federico Mancini | 2 | 78 | 9.79 |