Enumerating consecutive and nested partitions for graphs (Q1378295): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2025443436 / rank | |||
Normal rank |
Latest revision as of 20:29, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Enumerating consecutive and nested partitions for graphs |
scientific article |
Statements
Enumerating consecutive and nested partitions for graphs (English)
0 references
19 July 1998
0 references
Consecutive and nested partitions have been extensively studied in the set-partition problem as tools with which to search efficiently for an optimal partition. The authors extend the study of consecutive and nested partitions on a set of integers to the vertex-set of a graph \(G\). A subset of vertices of \(G\) is consecutive if the subgraph it induces is connected. A partition of the vertices of \(G\) is consecutive if each part is consecutive, and it is nested if the digraph with vertices the parts of the partition and an arc from \(P\) to \(Q\) if every connected subgraph containing \(P\) contains a vertex of \(Q\), is acyclic. In this sense the partition problem on a set of integers is simply the case where the graph is a path and the number of consecutive and nested partitions was determined by \textit{F. K. Hwang} and \textit{C. L. Mallows} [J. Comb. Theory, Ser. A 70, No. 2, 323-333 (1995; Zbl 0819.05005)]. In this paper the authors determine the number of consecutive and nested partitions when the graph \(G\) is a cycle. Also given is a partial order on general graphs with respect to these numbers.
0 references
partition
0 references
cycle
0 references
connected
0 references
graph
0 references