Premium
Distribution of Vertices Required a High‐Degree Condition on Partitions of Graphs Under Degree Constraints
Author(s) -
Furuya Michitaka,
Maezawa Shunichi
Publication year - 2025
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.23228
Subject(s) - mathematics , combinatorics , degree (music) , generalization , frequency partition of a graph , graph , discrete mathematics , degree distribution , order (exchange) , path graph , graph power , line graph , complex network , mathematical analysis , physics , acoustics , finance , economics
ABSTRACT LetGbe a graph, and letf 1 , f 2 : V ( G ) → { 0 , 1 , 2 , … }be functions. LetT 1 ( G )be the union of edges shared by two cycles of order at most four, and letT 0 ( G ) = V ( G ) \ T 1 ( G ). In this paper, we prove that if foru ∈ T h ( G )withh ∈ { 0 , 1 },d G ( u ) ≥ f 1 ( u ) + f 2 ( u ) − 1 + 2 handmin { f 1 ( u ) , f 2 ( u ) } ≥ 2 − 2 h, thenGcan be partitioned into two subgraphsG 1andG 2such thatd G i( u ) ≥ f i ( u )for eachu ∈ V ( G i ). The result is a generalization of some known results and gives a distribution of vertices required by a high‐degree condition on partitions of graphs under degree constraints.