2025/04/22 by Peiyi Duan, Duan, Peiyi, Yingzhi Tian +1 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Commutative Algebra and Its Applications #Digital Image Processing Techniques #FOS: Mathematics #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2504.15596
openalex publication_date 2025/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A sequence D=(d1,d2,…,dn) of non-negative integers is called a graphic sequence if there is a simple graph with vertices v1,v2,…,vn such that the degree of vi is di for 1≤ i≤ n. Given a graph theoretical property P, a graphic sequence D is forcibly P graphic if each graph with degree sequence D has property P. A graph is acyclic if it contains no cycles. A connected acyclic graph is just a tree and has n-1 edges. A graph of order n is unicyclic (resp. bicyclic) if it is connected and has n (resp. n+1) edges. Bar-Noy, Böhnlein, Peleg and Rawitz [Discrete Mathematics 346 (2023) 113460] characterized forcibly acyclic and forcibly connected acyclic graphic sequences. In this paper, we aim to characterize forcibly unicyclic and forcibly bicyclic graphic sequences.