✦ LIBER ✦

On clique-extremal (p,q)-graphs

✍ Scribed by F. Harary; A. Lempel

Publisher: John Wiley and Sons
Year: 1974
Tongue: English
Weight: 346 KB
Volume: 4
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230040408

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A clique of a graph is a maximal complete subgraph. A (p,q)‐graph has p points and q lines. A clique‐extremal (p,q)‐graph has either the maximum or the minimum number of cliques among all (p,q)‐graphs. Moon and Moser have determined constructively the maximum number of cliques in a p‐point graph. The problem of studying the clique‐extremal (p,q)‐graphs is now investigated. We first develop a standard form for such extremal graphs. These standard forms are shown to have a complementary kind of analogy with respect to maximum and minimum.

📜 SIMILAR VOLUMES

The maximum number of q-cliques in a gra

The maximum number of q-cliques in a graph with no p-clique

✍ Steven Roman 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 805 KB

Algorithms on clique separable graphs

✍ Fǎnicǎ Gavril 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 925 KB

We define a family of graphs. tailed the clique sepambk graphs. characterized by the fact that they have completely connected rut sets by which we decompose them into r)arts such that when no further decomposition is possible we have a set of simple subgraphs. For example the chordal gmphs and the i

Clique-gated graphs

✍ Johann Hagauer; Sandi Klavẑar 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 345 KB

Clique-gated graphs form an extension of quasi-median graphs. Two characterizations of these graphs are given and some other structural properties are obtained. An O(nm) algorithm is presented which recognizes clique-gated graphs. Here n and m denote the numbers of vertices and edges of a given grap

On clique partitions of split graphs

✍ W.D. Wallis; J. Wu 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 204 KB

Wallis, W.D. and J. Wu, On clique partitions of split graphs, Discrete Mathematics 92 (1991) 427-429. Split graphs are graphs formed by taking a complete graph and an empty graph disjoint from it and some or all of the possible edges joining the two. We prove that the problem of deciding the clique

Clique graphs of packed graphs

✍ Iwao Sato 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 129 KB

Let IGI be the number of vertices of a graph G and to(G) be the density of G. We call a graph G packed if the clique graph K(G) of G has exactly 2 IGI-O'(G) cliques. We correct the characterization of clique graphs of packed graphs given in Theorem 3.2 of Hedman [3]. All graphs considered here are f

Extremal interval graphs

✍ Jürgen Eckhoff 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 471 KB

## Abstract An interval graph is said to be extremal if it achieves, among all interval graphs having the same number of vertices and the same clique number, the maximum possible number of edges. We give an intrinsic characterization of extremal interval graphs and derive recurrence relations for t