Factors and connected factors in tough graphs with high isolated\n toughness

2018/12/30 by Morteza Hasanvand, Hasanvand, Morteza
Computer Science · Mathematics · Neuroscience · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Nuclear Receptors and Signaling

paper · pdf · doi:10.48550/arxiv.1812.11640

openalex publication_date 2018/12/30 · openalex created_date 2022/08/01 · openalex updated_date 2026/07/28

Abstract

Let G be a graph and let f be a positive integer-valued function on\nV(G). Assume that for all S\⊆ V(G),
sum_{v
in I(G
setminus\nS)}f(v)(f(v)+1)
le |S|, where I(G\∖ S) denotes the set of isolated\nvertices of G\∖ S. In this paper, we show that if for all S\⊆\nV(G),
omega(G
setminus S)
le
sum_{v
in S}(f(v)-1)+1, and \∑_v\∈\nV(G)f(v) is even, then G has a factor F such that for each vertex v,\nd_F(v)=f(v), where \ω(G\∖ S) denotes the number of components of\nG\∖ S. Moreover, we show that if for all S\⊆ V(G),\n
omega(G
setminus S)
le
frac14|S|+1, and f\≥ 2, then G has a\nconnected factor H such that for each vertex v, d_H(v)\∈\n f(v),f(v)+1 .\n

Citations

• Tough graphs and hamiltonian circuits
• The Factorization of Linear Graphs

Related

• Toughness and the existence of tree-connected \f,f+k\-factors
• The existence of tree-connected \g,f\-factors in edge-connected graphs and tough graphs
• On existence of [a,b]-factors avoiding given subgraphs
• Characterization of 1-Tough Graphs using Factors
• Tight toughness, isolated toughness and binding number bounds for the \K₂,C_n\-factors