Fill-in and operations of graphs (Q1902273)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fill-in and operations of graphs |
scientific article |
Statements
Fill-in and operations of graphs (English)
0 references
8 April 1996
0 references
The fill-in of a graph \(G\), \(f(G)\), is the minimum number of edges that must be added to the graph to make it chordal. In this paper, some properties of the fill-in of graphs are derived. The composite graph of \(G\) for \(H\) is the graph \(G[H]\), obtained from \(G\) by replacing each vertex of \(G\) by an isomorphic copy of \(H\). The paper expresses the fill- in of \(G[H]\), where \(G\) is chordal, in the fill-in of \(H\), the number of connected components of \(G\), and the number of edges of the complement of \(H\). Also, if \(H\) is a complete graph with \(n\) vertices, the fill-in of \(G[H]\) is \(n^2 f(G)\). A strongly planar graph is a graph that does not contain a wheel with four spikes (the graph obtained by making a vertex adjacent to all vertices in a chordless cycle of length four) as a minor. The author observes that every outerplanar graph is strongly planar. One can also observe that every graph of treewidth two is outerplanar. An algorithm that computes the fill-in of strongly planar graphs and that uses \(O(n^2)\) time is given.
0 references
fill-in
0 references
composite graph
0 references
strongly planar graph
0 references
wheel
0 references
minor
0 references
outerplanar graph
0 references
treewidth
0 references
algorithm
0 references