2025/09/27 by Peichao Wei, Wei, Peichao, Muhuo Liu +5
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2509.23078
openalex publication_date 2025/09/27 · openalex created_date 2025/10/19 · openalex updated_date 2026/07/28
Given a finite simple undirected graph G, let T1(G) denote the subset of vertices of G such that every vertex of T1(G) belongs to at least one subgraph isomorphic to a graph obtained by connecting a single vertex to two vertices of K4 - e. Define T0(G) = V(G) ∖ T1(G), and let a,b \colon V(G) \longrightarrow ℤ≥ 0 be arbitrary functions. In this paper, we prove that if dG(u) ≥ a(u) + b(u) + h(u), where h(u) ∈ \0,1\ for u ∈ Th(G), then there exists a partition (S, T) of V(G) such that dS(u) ≥ a(u) for every u ∈ S and dT(u) ≥ b(u) for every u ∈ T. This result extends the theorem of Stiebitz~[J. Graph Theory, 23 (1996), 321--324]. Moreover, we establish an analogous result in the case where T1(G) consists of vertices belonging to at least one K2,3, thereby extending the findings of Hou et al.~[Discrete Math., 341 (2018), 3288--3295].