Loading...
Please wait, while we are loading the content...
Similar Documents
Counting stable sets on cartesian products of graphs (1998).
| Content Provider | CiteSeerX |
|---|---|
| Author | Forbes, Florence Ycart, Bernard |
| Abstract | We study the generating functions for the number of stable sets of all cardinalities, in the case of graphs which are Cartesian products by paths, cycles, or trees. Explicit results are given for products by cliques. Algorithms based on matrix products are derived for grids, cylinders, toruses and hypercubes. Abbreviated title : Stable sets on Cartesian products Key Words : Stable sets, Cartesian products, Generating functions AMS Subject Classification : 05 A 15, 05 C 30 1 to whom correspondance should be sent 1 1 Introduction The stable sets of an undirected graph (also called independent sets in many references) are subsets of vertices no two of which are connected (see [1] for a general reference). A stable set which is not a strict subset of another stable set is called maximal, and a maximal stable set of highest cardinality is called maximum, its cardinality being the stable number, or independence number of the graph. The two problems of determining maximal and maximum stab... |
| File Format | |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Stable Set Cartesian Product Many Reference Independent Set Function Am Subject Classification Strict Subset Independence Number Undirected Graph Maximum Stab Cartesian Product Key Word Explicit Result Stable Number Generating Function General Reference Matrix Product Maximal Stable Set |
| Content Type | Text |
