Path factors in subgraphs
| Autor: | Quanru Pan, Qiuxiang Bian, Sizhong Zhou |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Applied Mathematics
Binding number 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics 010201 computation theory & mathematics Path (graph theory) Discrete Mathematics and Combinatorics Graph (abstract data type) Connectivity Mathematics |
| Zdroj: | Discrete Applied Mathematics. 319:183-191 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2021.04.012 |
| Popis: | A graph G is P ≥ k -factor deleted if for every edge e ∈ E ( G ) , G contains a P ≥ k -factor that excludes e . We first define the concept of ( P ≥ k , n ) -critical deleted graph, that is, a graph G is ( P ≥ k , n ) -critical deleted if for every subset D ⊆ V ( G ) with | D | = n , the graph G − D is P ≥ k -factor deleted. Clearly, a ( P ≥ k , 0 ) -critical deleted graph is a P ≥ k -factor deleted graph. In this paper, we verify that (i) an ( n + 2 ) -connected graph G is ( P ≥ 2 , n ) -critical deleted if its binding number b i n d ( G ) > 3 + n 4 ; (ii) an ( n + 2 ) -connected graph G is ( P ≥ 3 , n ) -critical deleted if its binding number b i n d ( G ) > 3 + n 2 . Furthermore, we claim that two results above are best possible in some sense. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect