✦ LIBER ✦

Threshold characterization of graphs with dilworth number two

✍ Scribed by C. Benzaken; P. L. Hammer; D. de Werra

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 692 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090207

No coin nor oath required. For personal study only.

✦ Synopsis

A graph with nodes 1. _.., n is a threshold signed graph if one can find two positive real numbers S,T and real numbers a , , ..., a, associated with the vertices in such a way that i,j are linked iff either la, + a,/ 3 S or la, -ail T. Such graphs generalize threshold graphs. It is shown that these graphs are precisely the graphs with Dilworth number at most two (the Dilworth number IS the maximum number of pairwise incomparable vertices in the vicinal preorder). Some other properties of this subclass of perfect graphs are also presented. The graphs considered in this paper are finite simple graphs G = (V,€), where V is the vertex set of G and E a subset of pairs of G. For x E V,N(x) denotes the neighbor set of x :

THRESHOLD GRAPHS, (BALANCED) SIGNED GRAPHS, THRESHOLD SIGNED GRAPHS 1.1. Threshold Graphs Threshold graphs were first introduced and studied in [2] and many works have focused on them (see for example [5,7,81).

📜 SIMILAR VOLUMES

Split graphs of Dilworth number 2

✍ C. Benzaken; P.L. Hammer; D. de Werra 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 250 KB

Characterization of graphs with hall num

Characterization of graphs with hall number 2

✍ Changiz Eslahchi; Matthew Johnson 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 165 KB

## Abstract Hall's condition is a simple requirement that a graph __G__ and list assignment __L__ must satisfy if __G__ is to have a proper __L__‐colouring. The Hall number of __G__ is the smallest integer __m__ such that whenever the lists on the vertices each has size at least __m__ and Hall's co

Cubic graphs with crossing number two

✍ Bruce Richter 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

Subdivision thresholds for two classes o

Subdivision thresholds for two classes of graphs

✍ C.A. Barefoot; L.H. Clark; A.J. Depew; R.C. Entringer; L.A. Székely 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 902 KB

The subdivision threshold for a graph F is the maximum number of edges, ex(n; FS), a graph of order n can have without containing a subdivision of F as a subgraph. We consider two instances: (i) F is the graph formed by a cycle C one vertex of which is adjacent to k vertices not on C, and (ii) F is

Graphs with least number of colorings

✍ A. Sakaloglu; A. Satyanarayana 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 535 KB

## Abstract A λ‐coloring of a graph G is an assignment of λ or fewer colors to the points of G so that no two adjacent points have the same color. Let Ω (n,e) be the collection of all connected n‐point and e‐edge graphs and let Ωp(n,e) be the planar graphs of Ω(n, e). This paper characterizes the g

Two characterizations of interchange gra

Two characterizations of interchange graphs of complete m-partite graphs

✍ Curtis R. Cook 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 564 KB

A graph G is m-partite if its points can be partitioned into m subsets Yl, . . . . Vm such that every line joins a point in Vi with a point in Vi, i + j. A complete m-partite graph contains every line joining Vi with V-. A complete graph Kp has every pair of its p points adjacent. The nth interchang