𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Graphs Without Multicliqual Edges

✍ Scribed by Lim Chong-Keang; Peng Yee-Hock

Publisher
John Wiley and Sons
Year
1981
Tongue
English
Weight
418 KB
Volume
5
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

An edge which belongs to more than one clique of a given graph is called a multicliqual edge. We find a necessary and sufficient condition for a graph H to be the clique graph of some graph G without multicliqual edges. We also give a characterization of graphs without multicliqual edges that have a unique critical generator. Finally, it is shown that there are infinitely many self‐clique graphs having more than one critical generator.

πŸ“œ SIMILAR VOLUMES

A vertex critical graph without critical
A vertex critical graph without critical edges
✍ Jason I. Brown πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 189 KB

Brown, J.I., A vertical critical graph without critical edges, Discrete Mathematics 102 (1992) 99-101. A vertex k-critical graph is a k-chromatic graph with the property that the removal of any vertex leaves a (k -1)-colourable graph. A critical edge in a graph is an edge whose deletion lowers the c

Edge colorings of complete graphs withou
Edge colorings of complete graphs without tricolored triangles
✍ AndrΓ‘s GyΓ‘rfΓ‘s; GΓ‘bor Simony πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 59 KB

## Abstract We show some consequences of results of Gallai concerning edge colorings of complete graphs that contain no tricolored triangles. We prove two conjectures of Bialostocki and Voxman about the existence of special monochromatic spanning trees in such colorings. We also determine the size

Edge disjoint Steiner trees in graphs wi
Edge disjoint Steiner trees in graphs without large bridges
✍ Matthias Kriesell πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 150 KB

## Abstract A set __A__ of vertices of an undirected graph __G__ is called __k__‐__edge‐connected in G__ if for all pairs of distinct vertices __a, b__∈__A__, there exist __k__ edge disjoint __a, b__‐paths in __G__. An __A__‐__tree__ is a subtree of __G__ containing __A__, and an __A__‐__bridge__ i

On independent cycles and edges in graph
On independent cycles and edges in graphs
✍ Thomas Andreae πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 339 KB

For integers k, s with 0 ~ ~~2 and n >~ 3~ -s. Justesen (1989) determined ex(n, k, 0) for all n >~ 3k and EX(n,k,O) for all n > (13k -4)/4, thereby settling a conjecture of Erdrs and P6sa; further EX (n,k,k) was determined by Erdrs and Gallai (n>~2k). In the present paper, by modifying the argument

On Critical Edges in Minimal Imperfect G
On Critical Edges in Minimal Imperfect Graphs
✍ AndrΓ‘s Sebő πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 725 KB

An edge of a graph is called critical, if deleting it the stability number of the graph increases, and a nonedge is called co-critical, if adding it to the graph the size of the maximum clique increases. We prove in this paper, that the minimal imperfect graphs containing certain configurations of t