An embedding of a graph G(into its complement G~c) is a permutation s on V(G) such that if any edge xy belongs to E, then s(x)s( y) does not belong to E(so G is a subgraph of its complement G~c). Faudree, Rousseau, Sc...An embedding of a graph G(into its complement G~c) is a permutation s on V(G) such that if any edge xy belongs to E, then s(x)s( y) does not belong to E(so G is a subgraph of its complement G~c). Faudree, Rousseau, Schelp and Schuster remarked that all non-embeddable graphs with n vertices and no more than n edges are either stars or contain 3 K or 4 C as subgraphs. For this reason they have conjectured that every non-star graph which contains no cycles of lengths 3 or 4 is a subgraph of its complement. This conjecture would nicely fit with other characterization theorems which specify that all graphs, except a family of forbidden graphs, satisfy a given property or are of a given type. In this article, we prove that the conjecture is true for a family of graphs of girth 5.展开更多
基金Supported by the National Natural Science Foundation of China (11871270)。
文摘An embedding of a graph G(into its complement G~c) is a permutation s on V(G) such that if any edge xy belongs to E, then s(x)s( y) does not belong to E(so G is a subgraph of its complement G~c). Faudree, Rousseau, Schelp and Schuster remarked that all non-embeddable graphs with n vertices and no more than n edges are either stars or contain 3 K or 4 C as subgraphs. For this reason they have conjectured that every non-star graph which contains no cycles of lengths 3 or 4 is a subgraph of its complement. This conjecture would nicely fit with other characterization theorems which specify that all graphs, except a family of forbidden graphs, satisfy a given property or are of a given type. In this article, we prove that the conjecture is true for a family of graphs of girth 5.
