๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On completely positive graphs and their complements

โœ Scribed by Felix Goldberg

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
81 KB
Volume
371
Category
Article
ISSN
0024-3795

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper we establish two results concerning completely positive graphs and their complements: (1) the complement of a completely positive graph on n 9 vertices is not completely positive; (2) the spectral radius of the adjacency matrix of a completely positive graph on n 6 vertices is at most 3 8 n. We show that (1) is best possible without additional assumptions. The proofs of (1) and (2) rely on a known fact of extremal graph theory which we state in the language of completely positive graphs and furnish with a proof: the size of a completely positive graph on n 6 vertices is at most n 2 /4 . We also give another short proof of (1), under the additional assumption that n 17.

๐Ÿ“œ SIMILAR VOLUMES

Clique Minors in Graphs and Their Comple
Clique Minors in Graphs and Their Complements
โœ Bruce Reed; Robin Thomas ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 107 KB

A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t 1 be an integer, and let G be a graph on n vertices with no minor isomorphic to K t+1 . Kostochka conjectures that there exists a constant c=c(t) independent of G such that the complement of G has

On graphs with complete bipartite star c
On graphs with complete bipartite star complements
โœ P.S. Jackson; P. Rowlinson ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 119 KB

Let ยต be an eigenvalue of the graph G with multiplicity m. A star complement for ยต in G is an induced subgraph G -X such that |X| = m and ยต is not an eigenvalue of G -X. Some general observations concerning graphs with the complete bipartite graph K r,s (r + s > 2) as a star complement are followed

On the edge-integrity of some graphs and
On the edge-integrity of some graphs and their complements
โœ R. Laskar; S. Stuecle; B. Piazza ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 483 KB

In this paper the authors study the edge-integrity of graphs. Edge-integrity is a very useful measure of the vulnerability of a network, in particular a communication network, to disruption through the deletion of edges. A number of problems are examined, including some Nordhaus-Gaddum type results.

Positive semidefinite matrix completions
Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming
โœ Houduo Qi ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 179 KB

Let G = (V , E) be a graph. In matrix completion theory, it is known that the following two conditions are equivalent: (i) G is a chordal graph; (ii) Every G-partial positive semidefinite matrix has a positive semidefinite matrix completion. In this paper, we relate these two conditions to constrain