Page 1

Displaying 1 – 14 of 14

Showing per page

The Least Eigenvalue of Graphs whose Complements Are Uni- cyclic

Yi Wang, Yi-Zheng Fan, Xiao-Xin Li, Fei-Fei Zhang (2015)

Discussiones Mathematicae Graph Theory

A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and contains...

Three-and-more set theorems

Pavol Hell, Jaroslav Nešetřil, André Raspaud, Eric Sopena (2000)

Commentationes Mathematicae Universitatis Carolinae

In this paper we generalize classical 3-set theorem related to stable partitions of arbitrary mappings due to Erdős-de Bruijn, Katětov and Kasteleyn. We consider a structural generalization of this result to partitions preserving sets of inequalities and characterize all finite sets of such inequalities which can be preserved by a “small” coloring. These results are also related to graph homomorphisms and (oriented) colorings.

Turán number of two vertex-disjoint copies of cliques

Caiyun Hu (2024)

Czechoslovak Mathematical Journal

The Turán number of a given graph H , denoted by ex ( n , H ) , is the maximum number of edges in an H -free graph on n vertices. Applying a well-known result of Hajnal and Szemerédi, we determine the Turán number ex ( n , K p K q ) of a vertex-disjoint union of cliques K p and K q for all values of n .

Currently displaying 1 – 14 of 14

Page 1