𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subdivision thresholds for two classes of graphs

✍ Scribed by C.A. Barefoot; L.H. Clark; A.J. Depew; R.C. Entringer; L.A. Székely

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
902 KB
Volume
125
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 the graph formed by a cycle C one vertex of which is adjacent to k vertices on C. In the first problem we determine the threshold and characterize the extremal graphs for all k> 1. In the second problem we do this for k = 2 only.

📜 SIMILAR VOLUMES

Two classes of chromatically unique grap
Two classes of chromatically unique graphs
✍ K.M. Koh; B.H. Goh 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 563 KB

## Let P(G; A) denote the chromatic polynomial of a graph G. G is chromatically unique if G is isomorphic to H for any graph H with P(H; A) = P(G; A). In this paper, we provide two new classes of chromatically unique graphs.

A class of threshold and domishold graph
A class of threshold and domishold graphs: equistable and equidominating graphs
✍ Charles Payan 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 484 KB

A thwahold grerph (rtzspativ4y domlshukf graph) is 01 graph for which the independent 881% (rapsctiwzly ths dominuting a&a) cctn bgr chnfuctsrixsd by the 0, l-aolutiona of a linaur ## kpallty (ass [ij and [S]), We define here the #rugher far which the mawlmal indapsndent eettr (rsopsctivsly tha m

Threshold characterization of graphs wit
Threshold characterization of graphs with dilworth number two
✍ C. Benzaken; P. L. Hammer; D. de Werra 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 692 KB

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 thes

Hamiltonian threshold for strong product
Hamiltonian threshold for strong products of graphs
✍ Daniel Král'; Ladislav Stacho 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 161 KB

## Abstract We prove that the strong product of any at least ${({\rm ln}}\, {2})\Delta+{O}(\sqrt{\Delta})$ non‐trivial connected graphs of maximum degree at most Δ is pancyclic. The obtained result is asymptotically best possible since the strong product of ⌊(ln 2)__D__⌋ stars __K__~1,__D__~ is not