Strong ƒ-Star Factors of Graphs

Zheng Yan

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 3, page 475-482
  • ISSN: 2083-5892

Abstract

top
Let G be a graph and f : V (G) → {2, 3, . . .}. A spanning subgraph F is called strong f-star of G if each component of F is a star whose center x satisfies degF (x) ≤ ƒ(x) and F is an induced subgraph of G. In this paper, we prove that G has a strong f-star factor if and only if oddca(G − S) ≤ ∑x∊S ƒ(x) for all S ⊂ V (G), where oddca(G) denotes the number of odd complete-cacti of G.

How to cite

top

Zheng Yan. "Strong ƒ-Star Factors of Graphs." Discussiones Mathematicae Graph Theory 35.3 (2015): 475-482. <http://eudml.org/doc/271238>.

@article{ZhengYan2015,
abstract = {Let G be a graph and f : V (G) → \{2, 3, . . .\}. A spanning subgraph F is called strong f-star of G if each component of F is a star whose center x satisfies degF (x) ≤ ƒ(x) and F is an induced subgraph of G. In this paper, we prove that G has a strong f-star factor if and only if oddca(G − S) ≤ ∑x∊S ƒ(x) for all S ⊂ V (G), where oddca(G) denotes the number of odd complete-cacti of G.},
author = {Zheng Yan},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {ƒ-star factor; strong ƒ-star factor; complete-cactus; factor of graph.; -star factor; strong -star factor; factor of graph},
language = {eng},
number = {3},
pages = {475-482},
title = {Strong ƒ-Star Factors of Graphs},
url = {http://eudml.org/doc/271238},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Zheng Yan
TI - Strong ƒ-Star Factors of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 3
SP - 475
EP - 482
AB - Let G be a graph and f : V (G) → {2, 3, . . .}. A spanning subgraph F is called strong f-star of G if each component of F is a star whose center x satisfies degF (x) ≤ ƒ(x) and F is an induced subgraph of G. In this paper, we prove that G has a strong f-star factor if and only if oddca(G − S) ≤ ∑x∊S ƒ(x) for all S ⊂ V (G), where oddca(G) denotes the number of odd complete-cacti of G.
LA - eng
KW - ƒ-star factor; strong ƒ-star factor; complete-cactus; factor of graph.; -star factor; strong -star factor; factor of graph
UR - http://eudml.org/doc/271238
ER -

References

top
  1. [1] J. Akiyama and M. Kano, Factors and Factorizations of Graphs (Lecture Note in Math. 2031 Springer- Verlag Berlin Heidelberg, 2011). doi:10.1007/978-3-642-21919-1[Crossref] Zbl1229.05001
  2. [2] A. Amahashi and M. Kano, On factors with given components, Discrete Math. 42 (1982) 1-6. doi:10.1016/0012-365X(82)90048-6[Crossref] Zbl0525.05048
  3. [3] C. Berge and M. Las Vergnas, On the existence of subgraphs with degree constraints, Indag. Math. Proc. 81 (1978) 165-176. doi:10.1016/S1385-7258(78)80007-9[Crossref] 
  4. [4] Y. Egawa, M. Kano and A.K. Kelmans, Star partitions of graphs, J. Graph Theory 25 (1997) 185-190. doi:10.1002/(SICI)1097-0118(199707)25:3h185::AID-JGT2i3.0.CO;2-H[Crossref] Zbl0877.05045
  5. [5] J. Folkman and D.R. Fulkerson, Flows in infinite graphs, J. Combin. Theory 8 (1970) 30-44. doi:10.1016/S0021-9800(70)80006-0[Crossref] Zbl0185.27904
  6. [6] M. Las Vergnas, An extension of Tutte’s 1-factor theorem, Discrete Math. 23 (1978) 241-255. doi:10.1016/0012-365X(78)90006-7[Crossref] 
  7. [7] A.K. Kelmans, Optimal packing of induced stars in a graph, RUTCOR Research Report 26-94, Rutgers University (1994) 1-25. 
  8. [8] A. Saito and M. Watanabe, Partitioning graphs into induced stars, Ars Combin. 36 (1993) 3-6. Zbl0794.05107

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.