|
Fill-in Numbers of Some Graphs
TANG Jie-quan, SHU Jin-long
2006, 2006 (5):
76-82.
By using the decomposition theorem and the local reductive elimination for the fill-in of graphs, the fill-in numbers of some special graphs, such as G1×G2, S(G) and double cyclic graphs were studied. And the following results were obtained: (1)F(Pm×Pn)≦(m-2)(n-2), where m≧2, n≧2; ; (2) if G is a 2-connected graph with m edges and n vertices, then F(S(G))=m+F(G); (3) let G be a double cyclic graph, the length of the two cycles being p and q, respectively, and t the number of the vertices which are both in the two cycles (the end points are excluded), then F(G)=p+q-t-6.
Related Articles |
Metrics
|