2017/09/01 by Todd Tichenor, Tichenor, Todd
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.1709.00393
arxiv created 2017/09/01 · openalex publication_date 2017/09/01 · arxiv updated 2017/09/04 · openalex created_date 2017/09/15 · openalex updated_date 2026/07/28
A graph composition is a partition of the vertex set such that each member of the partition induces a connected sub- graph, and the composition number of a graph is the number of possible graph compositions. A partition of a set S of consecutive labelled vertices is said to have a minimax vertex v in S if the label of v is the smallest label in the set of all maximum labels over all members of the partition. This paper exhibits a recursive formula for the composition number of a certain class of graphs and estab- lishes a connection between the composition numbers of this class of graphs and that of the minimax of partitions of a labelled set (the minimum label of the set of all maximum labels over every member of the partition).