Wyniki wyszukiwania

1

The Minimum Spectral Radius of Signless Laplacian of Graphs with a Given Clique Number

100%

Su L., Li H.-H., Zhang J.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 1

95-102

EN

In this paper we observe that the minimal signless Laplacian spectral radius is obtained uniquely at the kite graph PKn−ω,ω among all connected graphs with n vertices and clique number ω. In addition, we show that the spectral radius μ of PKm,ω (m ≥ 1) satisfies [...] More precisely, for m > 1, μ satisfies the equation [...] where [...] and [...] . At last the spectral radius μ(PK∞,ω) of the infinite graph PK∞,ω is also discussed.

2

A Different Short Proof of Brooks’ Theorem

100%

Rabern L.

Discussiones Mathematicae Graph Theory

|

2014

|

tom 34

|

nr 3

633-634

EN

Lovász gave a short proof of Brooks’ theorem by coloring greedily in a good order. We give a different short proof by reducing to the cubic case.

3

The Quest for A Characterization of Hom-Properties of Finite Character

51%

Broere I., Matsoha M. D. V., Heidema J.

Discussiones Mathematicae Graph Theory

|

2016

|

tom 36

|

nr 2

479-500

EN

A graph property is a set of (countable) graphs. A homomorphism from a graph G to a graph H is an edge-preserving map from the vertex set of G into the vertex set of H; if such a map exists, we write G → H. Given any graph H, the hom-property →H is the set of H-colourable graphs, i.e., the set of all graphs G satisfying G → H. A graph property P is of finite character if, whenever we have that F ∈ P for every finite induced subgraph F of a graph G, then we have that G ∈ P too. We explore some of the relationships of the property attribute of being of finite character to other property attributes such as being finitely-induced-hereditary, being finitely determined, and being axiomatizable. We study the hom-properties of finite character, and prove some necessary and some sufficient conditions on H for →H to be of finite character. A notable (but known) sufficient condition is that H is a finite graph, and our new model-theoretic proof of this compactness result extends from hom-properties to all axiomatizable properties. In our quest to find an intrinsic characterization of those H for which →H is of finite character, we find an example of an infinite connected graph with no finite core and chromatic number 3 but with hom-property not of finite character.

Ograniczanie wyników

3 Discussiones Mathematicae Graph Theory

1 Broere I.

1 Heidema J.

1 Li H.-H.

1 Matsoha M. D. V.

1 Rabern L.

1 Su L.

1 Zhang J.

1 2016

2 2014

The Minimum Spectral Radius of Signless Laplacian of Graphs with a Given Clique Number

A Different Short Proof of Brooks’ Theorem

The Quest for A Characterization of Hom-Properties of Finite Character