On CIS circulants Boros, Endre; Gurvich, Vladimir; Milanič, Martin
Discrete mathematics,
03/2014, Volume:
318
Journal Article
Peer reviewed
Open access
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 α=α(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 G¯ are both well-covered and the product α(G)α(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 P4-free graphs are CIS. In this paper, in addition to the simple family of P4-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.
Strong cliques in diamond-free graphs Chiarelli, Nina; Martínez-Barona, Berenice; Milanič, Martin ...
Theoretical computer science,
02/2021, Volume:
858
Journal Article
Peer reviewed
Open access
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of ...diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or co-NP-hard when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques?
On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamond-free graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.
•A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets.•We study strong cliques in the class of diamond-free graphs.•We characterize diamond-free CIS graphs and study their Erdős-Hajnal property.•We characterize co-strongly perfect diamond-free graphs.•We derive hardness results for five related problems.
The class of
2
K
2
-free graphs includes several interesting subclasses such as split, pseudo-split, threshold graphs, complements to chordal, interval or trivially perfect graphs. The fundamental ...property of
2
K
2
-free graphs is that they contain polynomially many maximal independent sets. As a consequence, several important problems that are NP-hard in general graphs, such as 3-colorability, maximum weight independent set (WIS), minimum weight independent dominating set (WID), become polynomial-time solvable when restricted to the class of
2
K
2
-free graphs. In the present paper, we extend
2
K
2
-free graphs to larger classes with polynomial-time solvable WIS or WID. In particular, we show that WIS can be solved in polynomial time for
(
K
2
+
K
1
,
3
)
-free graphs and WID for
(
K
2
+
K
1
,
2
)
-free graphs. The latter result is in contrast with the fact that independent domination is NP-hard in the class of
2
K
1
,
2
-free graphs, which has been recently proven by Zverovich.
A graph is CIS if every maximal clique interesects every maximal stable set. Currently, no good characterization or recognition algorithm for the CIS graphs is known. We characterize graphs in which ...every maximal matching saturates all vertices of degree at least two and use this result to give a structural, efficiently testable characterization of claw-free CIS graphs. We answer in the negative a question of Dobson, Hujdurović, Milanič, and Verret Vertex-transitive CIS graphs, European J. Combin. 44 (2015) 87–98 asking whether the number of vertices of every CIS graph is bounded from above by the product of its clique and stability numbers. On the positive side, we show that the question of Dobson et al. has an affirmative answer in the case of claw-free graphs.
X. Deng et al. proved Chvátal’s conjecture on maximal stable sets and maximal cliques in graphs. G. Ding made a conjecture to generalize Chvátal’s conjecture. The purpose of this paper is to prove ...this conjecture in planar graphs and the complement of planar graphs.
Vehicular Ad-hoc Networks (VANET) offer several user applications for passengers and drivers, as well as security and internet access applications. To ensure efficient data transmission between ...vehicles, a reliable routing protocol is considered a significant challenge. This paper suggests a new clustering-based routing protocol combining a modified K-Means algorithm with Continuous Hopfield Network and Maximum Stable Set Problem (KMRP) for VANET. In this way, the basic input parameters of the K-Means algorithm, such as the number of clusters and the initial cluster heads, will not be selected randomly, but using Maximum Stable Set Problem and Continuous Hopfield Network. Then the assignment of vehicles to clusters will be carried out according to Link Reliability Model as a metric that replaces the distance parameter in the K-Means algorithm. Finally, the cluster head is selected by weight function according to the amount of free buffer space, the speed, and the node degree. The simulation results have proved that the designed protocol performs better in a highway vehicular environment, compared to the most recent schemes designed for the same objective. In fact, KMRP reduces traffic congestion, and thus provides a significant increase in Throughput. In addition, KMRP decreases the transmission delay and guarantees the stability of the clusters in high density and mobility, which acts better in terms of the Packet Delivery Ratio.
If a pursuit game with many persons can be formalized in the framework of zero-sum differential games, then general methods can be applied to solve it. But difficulties arise connected with very high ...dimension of the phase vector when there are too many objects. Just due to this problem, special formulations and methods have been elaborated for conflict interaction of groups of objects. This paper is a survey of publications and results on group pursuit games.
A common computational approach for polynomial optimization problems (POPs) is to use (hierarchies of) semidefinite programming (SDP) relaxations. When the variables in the POP are required to be ...nonnegative - as is the case for combinatorial optimization problems, for example - these SDP problems typically involve nonnegative matrices, i.e. they are conic optimization problems over the doubly nonnegative cone. The Jordan reduction, a symmetry reduction method for conic optimization, was recently introduced for symmetric cones by Parrilo and Permenter Mathematical Programming 181(1), 2020. We extend this method to the doubly nonnegative cone, and investigate its application to known relaxations of the quadratic assignment and maximum stable set problems. We also introduce new Julia software where the symmetry reduction is implemented.
PDF
