Supercliques in a Graph

Authors

  • Ramil Dela Cerna Mindanao State University-Iligan Institute of Technology
  • Sergio Canoy Mindanao State University-Iligan Institute of Technology

DOI:

https://doi.org/10.29020/nybg.ejpam.v15i3.4480

Abstract

A set S ⊆ V (G) of a (simple) undirected graph G is a superclique in G if it is a clique and for every pair of distinct vertices v, w ∈ S, there exists u ∈ V (G) \ S such that u ∈ NG(v) \ NG(w) or u ∈ NG(w) \ NG(v). The maximum cardinality among the supercliques in G, denoted by ωs(G), is called the superclique number of G. In this paper, we determine the superclique numbers of some graphs including those resulting from some binary operations of graphs. We will also show that the difference of the clique number and the superclique number can be made arbitrarily large.

Author Biography

Sergio Canoy, Mindanao State University-Iligan Institute of Technology

Downloads

How to Cite

Dela Cerna, R., & Canoy, S. (2022). Supercliques in a Graph. European Journal of Pure and Applied Mathematics, 15(3), 1217–1228. https://doi.org/10.29020/nybg.ejpam.v15i3.4480