complete

equivalent to: complete

providers: ISGCI

Relations

Results

• 2022 Expanding the Graph Parameter Hierarchy by Tran
  • page 18 : graph class complete has unbounded vertex cover – Note that a clique of size $n$ has … a vertex cover number of $n-1$
  • page 18 : graph class complete has constant twin-cover number – Note that a clique of size $n$ has a twin cover number of 0 …
• 2017 Graph Theory by Diestel
  • page 3 : complete – If all the vertices of $G$ are pairwise adjacent, then $G$ is \emph{complete}.
• 2012 Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics by Ganian
  • page 263 : graph class complete has constant twin-cover number – We note that complete graphs indeed have a twin-cover of zero.
• 2010 Comparing 17 graph parameters by Sasák
  • page 17 : graph class complete has unbounded treewidth – Theorem 2.2
• 1993 The Pathwidth and Treewidth of Cographs by Bodlaender, Möhring
  • page 4 : graph class complete has unbounded treewidth – Lemma 3.1 (“clique containment lemma”). Let $({X_i\mid u\in I},T=(I,F))$ be a tree-decomposition of $G=(V,E)$ and let $W \subseteq V$ be a clique in $G$. Then there exists $i \in I$ with $W \subseteq X_i$.
• unknown source
  • graph class complete has unbounded maximum clique – Parameter is unbounded for the graph class of cliques.
  • graph class complete has unbounded domatic number – Parameter is unbounded for the graph class of cliques.
  • graph class complete has unbounded edge connectivity – Parameter is unbounded for the graph class of cliques.
  • graph class complete has unbounded maximum matching
• assumed
  • graph class complete is included in graph class connected – by definition
  • graph class complete is included in graph class cluster – by definition
  • graph class complete is included in graph class co-cluster
  • graph class co-cluster is not included in graph class complete
  • graph class complete has constant distance to complete – by definition