Boros, Endre ; Gurvich, Vladimir ; Milanič, Martin, 1980-
A circulant is a Cayley graph over a cyclic group. A well-covered graph is a graph in which all maximal stable sets are of the same size ▫$\alpha=\alpha(G)$▫, or in other words, they are all maximum. ...A CIS graph is a graph in which every maximal stable set and every maximal clique intersect. It is not difficult to show that a circulant ▫$G$▫ is a CIS graph if and only if ▫$G$▫ and its complement ▫$\overline{G}$▫ are both well-covered and the product ▫$\alpha (G) \alpha (\overline{G})$▫ is equal to the number of vertices. It is also easy to demonstrate that both families, the circulants and the CIS graphs, are closed with respect to the operations of taking the complement and the lexicographic product. We study the structure of the CIS circulants. It is well-known that all ▫$P_4$▫-free graphs are CIS. In this paper, in addition to the simple family of ▫$P_4$▫-free circulants, we construct a non-trivial sparse but infinite family of CIS circulants. We are not aware of any CIS circulant that could not be obtained from graphs in this family by the operations of taking the complement and the lexicographic product.
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
PDF
