Independence and graph homomorphisms graph homomorphisms

A graph with n vertices that contains no triangle and no 5-cycle and minimum degree exceeding n/4 contains an independent set with at least (3n)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7-cycle and invoking the No Homomorphism Lemma. For k ≥ 4, a graph with n vertices, odd girth 2k+1, and minimum degree exceeding n/(k+1) contains an independent set with at least kn/(2k+1) vertices; however, we suspect this is not best possible. © 1993 John Wiley & Sons, Inc.     

Conic formulations of graph homomorphisms

Given graphs X and Y, we define two conic feasibility programs which we show have a solution over the completely positive cone if and only if there exists a homomorphism from X to Y. By varying the cone, we obtain similar characterizations of quantum/entanglement-assisted homomorphisms and three previously studied relaxations of these relations. Motivated by this, we investigate the properties of these “conic homomorphisms” for general (suitable) cones. We also consider two generalized versions of the Lovász theta function, and how they interact with these conic homomorphisms. We prove analogs of several results on classical graph homomorphisms as well as some monotonicity theorems. We also show that one of the generalized theta functions is multiplicative on lexicographic and disjunctive graph products.     

On the extension of vertex maps to graph homomorphisms

A reflexive graph is a simple undirected graph where a loop has been added at each vertex. If G and H are reflexive graphs and U⊆V(H), then a vertex map f:U→V(G) is called nonexpansive if for every two vertices x,y∈U, the distance between f(x) and f(y) in G is at most that between x and y in H. A reflexive graph G is said to have the extension property (EP) if for every reflexive graph H, every U⊆V(H) and every nonexpansive vertex map f:U→V(G), there is a graph homomorphism φ_f:H→G that agrees with f on U. Characterizations of EP-graphs are well known in the mathematics and computer science literature. In this article we determine when exactly, for a given “sink”-vertex s∈V(G), we can obtain such an extension φ_f;s that maps each vertex of H closest to the vertex s among all such existing homomorphisms φ_f. A reflexive graph G satisfying this is then said to have the sink extension property (SEP). We then characterize the reflexive graphs with the unique sink extension property (USEP), where each such sink extensions φ_f;s is unique.     

Measure preserving homomorphisms and independent sets in tensor graph powers

In this note, we study the behavior of independent sets of maximum probability measure in tensor graph powers. To do this, we introduce an upper bound using measure preserving homomorphisms. This work extends some previous results concerning independence ratios of tensor graph powers.     

Acyclic homomorphisms to stars of graph Cartesian products and chordal bipartite graphs

Homomorphisms to a given graph $H$ ($H$-colourings) are considered in the literature among other graph colouring concepts. We restrict our attention to a special class of $H$-colourings, namely $H$ is assumed to be a star. Our additional requirement is that the set of vertices of a graph $G$ mapped into the central vertex of the star and any other colour class induce in $G$ an acyclic subgraph. We investigate the existence of such a homomorphism to a star of given order. The complexity of this problem is studied. Moreover, the smallest order of a star for which a homomorphism of a given graph $G$ with desired features exists is considered. Some exact values and many bounds of this number for chordal bipartite graphs, cylinders, grids, in particular hypercubes, are given. As an application of these results, we obtain some bounds on the cardinality of the minimum feedback vertex set for specified graph classes.     

Prefix-primitivity-preserving homomorphisms

This paper aims to investigate homomorphisms which preserve p-primitive languages. A characterization of p-primitivity-preserving homomorphisms can be detected within finite steps. Also the set of square-freeness-preserving homomorphisms is shown to be a proper subfamily of the set of p-primitivity-preserving homomorphisms. For homomorphisms over an alphabet X with |X|=2, it is also shown that the set of p-primitivity-preserving homomorphisms is a proper subfamily of the set of primitivity-preserving homomorphisms. But it is conjectured to also hold for homomorphisms over an alphabet with more than two letters.     

Fully idempotent homomorphisms

For arbitrary modules A and B we introduce and study the notion of a fully idempotent Hom (A, B). As a corollary we obtain some well-known properties of fully idempotent rings and modules.     

Equivalence of metric homomorphisms

Suppose K is an algebra with involution overk and A, B are K-modules on which are defined -Hermitian K-invariant forms with values ink. Metric homomorphisms of the module A into the module are called equivalent in the broad sense if one can be obtained from the other by multiplying by automorphisms of both modules, and equivalent in the narrow sense if one can be obtained from the other by multiplying by an automorphism of B. Necessary and sufficient conditions are given for the broad and narrow equivalence of two metric homomorphisms of one semisimple module of finite length into another. As a consequence, a classification of representations of one quadratic form by means of another is obtained.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 114, pp. 205–210, 1982.In conclusion, the author would like to express her sincere gratitude to A. V. Yakovlev, under whose guidance this paper was written, for many valuable discussions and for his useful advice.     

On Blaschke-Minkowski homomorphisms

In this article we establish a Brunn-Minkowski-type inequality for mixed Blaschke-Minkowski homomorphisms.     

序同态的NC－连续性

本文在ＬＦ拓扑空间上利用良紧性作为背景引进了序同态的ＮＣ－连续性、分子网和理想的ＮＣ－收敛性及ＮＣ－闭包算子等概念，系统地讨论了这些概念之间的关系以及ＮＣ－连续序同态的特性，得到了若干重要的结果。     

Trace-preserving homomorphisms of semigroups

We consider those homomorphisms φ of semigroups of trace-class operators on a Hilbert space that preserve trace. If φ is a spatially induced isomorphism on a semigroup , that is φ(S)T=TS for an invertible operator T and for all S in , then φ clearly has this property. More generally, if T in the relation above is a densely defined, closed, injective operator with dense image, φ still preserves trace. We prove the converse of this statement under certain conditions. Using these results we prove simultaneous similarity theorems for semigroups of operators (on finite or infinite-dimensional spaces) whose members are individually similar to unitary or J-unitary operators.