2021/01/06 by Lilian Markenzon, Markenzon, Lilian, Christina F. E. M. Waga +1
Computer Science · Mathematics · #05C40 #05C75 #05C85 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2101.02095
openalex publication_date 2021/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The scattering number of a graph G was defined by Jung in 1978 as sc(G) =\nmax \ω(G - S) - |S|, S \⊆ V, \ω(G - S) \≠1 where\n\ω(G - S) is the number of connected components of the graph G-S. It\nis a measure of vulnerability of a graph and it has a direct relationship with\nthe toughness of a graph. Strictly chordal graphs, also known as block\nduplicate graphs, are a subclass of chordal graphs that includes block and\n3-leaf power graphs. In this paper we present a linear time solution for the\ndetermination of the scattering number and scattering set of strictly chordal\ngraphs. We show that, although the knowledge of the toughness of the class is\nhelpful, it is not sufficient to provide an immediate result for determining\nthe scattering number.\n