Volume 7 Number 6 (Jun. 2012)
Home > Archive > 2012 > Volume 7 Number 6 (Jun. 2012) >
JCP 2012 Vol.7(6): 1497-1502 ISSN: 1796-203X
doi: 10.4304/jcp.7.6.1497-1502

Erdös Conjecture on Connected Residual Graphs

Jiangdong Liao1, Gonglun Long2, Mingyong Li3
1College of Mathematics and Computer Sciences, Yangtze Normal University, Fuling 408100, Chongqing, P.R. China
2Information Technology Center of Chongqing Normal University, Chongqing 401331, P.R. China
3College of Computer and Information Science, Chongqing Normal University, Chongqing 401331, P.R. China


Abstract—A graph G is said to be F-residual if for every point u in G, the graph obtained by removing the closed neighborhood of u from G is isomorphic to F. Similarly, if the remove of m consecutive closed neighborhoods yields Kn, then G is called m-Kn-residual graph. Erdös determine the minimum order of the m-Kn-residual graph for all m and n, the minimum order of the connected Kn-residual graph is found and all the extremal graphs are specified. Jiangdong Liao and Shihui Yang determine the minimum order of the connected 2-Kn-residual graph is found and all the extremal graphs are specified expected for n=3, and in this paper, we prove that the minimum order of the connected 3-Kn-residual graph is found and all the extremal graphs are specified expected for n=5, 7, 9,10, and we revised Erdös conjecture.

Index Terms—Residual-graph, Closed neighborhood, Adjacent, Cartesian product.

[PDF]

Cite: Jiangdong Liao, Gonglun Long, Mingyong Li, "Erdös Conjecture on Connected Residual Graphs," Journal of Computers vol. 7, no. 6, pp. 1497-1502, 2012.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
  • Nov 14, 2019 News!

    Vol 14, No 11 has been published with online version   [Click]

  • Mar 20, 2020 News!

    Vol 15, No 2 has been published with online version   [Click]

  • Dec 16, 2019 News!

    Vol 14, No 12 has been published with online version   [Click]

  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Read more>>