In this paper we study the existence of homomorphisms @math using semidefinite programming. Specifically, we use the vector chromatic number of a graph, defined as the smallest real number @math for which there exists an assignment of unit vectors @math to its vertices such that @math when @math . Our approach allows to reprove, without using the Erdős-Ko-Rado Theorem, that for @math the Kneser graph @math and the @math -Kneser graph @math are cores, and furthermore, that for @math there exists a homomorphism @math if and only if @math divides @math . In terms of new applications, we show that the even-weight component of the distance @math -graph of the @math -cube @math is a core and also, that non-bipartite Taylor graphs are cores. Additionally, we give a necessary and sufficient condition for the existence of homomorphisms @math when @math . Lastly, we show that if a 2-walk-regular graph (which is non-bipartite and not complete multipartite) has a unique optimal vector coloring, it is a core. Based on this sufficient condition we conducted a computational study on Ted Spence's list of strongly regular graphs and found that at least 84 are cores.
For an arbitrary graph @math , the is the vertex minimal subgraph to which @math admits a homomorphism. Every graph has a unique core, and the core of @math is itself a core. Moreover, @math and @math have the same core if and only if they are , i.e., @math and @math . Cores are the unique minimal elements of these homomorphic equivalence classes. In this sense, the core of a graph is the smallest graph retaining all of its homomorphic information. In we show that if @math is UVC, and its unique optimal vector coloring is injective on its vertex neighborhoods, then @math is a core (Theorem ). To illustrate the usefulness of our sufficient condition, we given an easy proof of the fact that for @math , both @math and @math are cores. This is well-known @cite_11 , but our proof avoids invoking the Erd o s-Ko-Rado Theorem to describe the structure of the maximum independent sets of these graphs, and it also avoids using the No Homomorphism Lemma. As a second application, we also show that the graphs @math constructed in are cores.
@cite_11
2070948578
Let @math be a 3-uniform hypergraph of order @math and size @math , and let @math be a subset of vertices of @math . The set @math is a strong transversal in @math if @math contains at least two vertices from every edge of @math . The strong transversal number @math of @math is the minimum size of a strong transversal in @math . We show that @math , and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph @math of order @math and size @math that achieves equality in this bound. A set @math of vertices in a graph @math is a double total dominating set of @math if every vertex of @math is adjacent to at least two vertices in @math . The minimum cardinality of a double total dominating set of @math is the double total domination number @math of @math . Let @math be a connected graph of order @math with minimum degree at least three. As an application of our hypergraph results, we show that @math with equality if and only if @math is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if @math is not the Heawood graph, we show that @math , while if @math is a cubic graph different from the Heawood graph, we show that @math , and this bound is sharp.