Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-22T05:41:11.380Z Has data issue: false hasContentIssue false
  • English
  • Français

NEIGHBOURHOOD AND THE EXISTENCE OF FRACTIONAL k-FACTORS OF GRAPHS

Part of: Graph theory

Published online by Cambridge University Press:  13 January 2010

SIZHONG ZHOU ,
BINGYUAN PU  and
YANG XU
SIZHONG ZHOU*
Affiliation:
School of Mathematics and Physics, Jiangsu University of Science and Technology, Mengxi Road 2, Zhenjiang, Jiangsu 212003, PR China (email: [email protected])
BINGYUAN PU
Affiliation:
Department of Fundamental Course, Chengdu Textile College, Chengdu, Sichuan 611731, PR China
YANG XU
Affiliation:
Department of Mathematics, Qingdao Agricultural University, Qingdao, Shandong 266109, PR China (email: [email protected])
*
✉For correspondence; e-mail: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let G be a graph, and k a positive integer. Let h:E(G)→[0,1] be a function. If ∑ e∋xh(e)=k holds for each x∈V (G), then we call G[Fh] a fractional k-factor of G with indicator function h where Fh={e∈E(G)∣h(e)>0}. In this paper we use neighbourhoods to obtain a new sufficient condition for a graph to have a fractional k-factor. Furthermore, this result is shown to be best possible in some sense.

Keywords

graphneighbourhoodfractional k-factor

MSC classification

Secondary: 05C70: Factorization, matching, partitioning, covering and packing
Type
Research Article
Information
Bulletin of the Australian Mathematical Society , Volume 81 , Issue 3 , June 2010 , pp. 473 - 480
Copyright
Copyright © Australian Mathematical Publishing Association Inc. 2010

Footnotes

This research was sponsored by Qing Lan Project of Jiangsu Province and was supported by Jiangsu Provincial Educational Department (07KJD110048) and Sichuan Provincial Educational Department (08zb068).

References

[1]Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications (Macmillan Press, London, 1976).Google Scholar
[2]Liu, H. and Liu, G., ‘Binding number and minimum degree for the existence of (g,f,n)-critical graphs’, J. Appl. Math. Comput. 29 (2009), 207–216.Google Scholar
[3]Liu, G. and Zhang, L., ‘Fractional (g,f)-factors of graphs’, Acta Math. Sci. Ser. B Engl. Ed. 21 (2001), 541–545.CrossRefGoogle Scholar
[4]Liu, G. and Zhang, L., ‘Toughness and the existence of fractional k-factors of graphs’, Discrete Math. 308 (2008), 1741–1748.CrossRefGoogle Scholar
[5]Matsuda, H., ‘Fan-type results for the existence of [a,b]-factors’, Discrete Math. 306 (2006), 688–693.Google Scholar
[6]Woodall, D. R., ‘k-factors and neighbourhoods of independent sets in graphs’, J. London Math. Soc. (2) 41 (1990), 385–392.CrossRefGoogle Scholar
[7]Yu, J., Liu, G., Ma, M. and Cao, B., ‘A degree condition for graphs to have fractional factors’, Adv. Math. (China) 35 (2006), 621–628.Google Scholar
[8]Zhou, S., ‘Independence number, connectivity and (a,b,k)-critical graphs’, Discrete Math. 309 (2009), 4144–4148.Google Scholar
[9]Zhou, S., ‘Some results on fractional k-factors’, Indian J. Pure Appl. Math. 40 (2009), 113–121.Google Scholar
[10]Zhou, S. and Liu, H., ‘Neighborhood conditions and fractional k-factors’, Bull. Malays. Math. Sci. Soc. (2) 32 (2009), 37–45.Google Scholar
[11]Zhou, S. and Shen, Q., ‘On fractional (f,n)-critical graphs’, Inform. Process. Lett. 109 (2009), 811–815.Google Scholar
[12]Zhou, S. and Xu, Y., ‘Neighbourhoods of independent sets for (a,b,k)-critical graphs’, Bull. Aust. Math. Soc. 77 (2008), 277–283.Google Scholar