✦ LIBER ✦

Generalized homomorphism graph functions

✍ Scribed by Lih-Hsing Hsu

Book ID: 103056155
Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 447 KB
Volume: 84
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90270-r

No coin nor oath required. For personal study only.

✦ Synopsis

A real-valued function f defined on the set of all graphs, 3, such that

for all G, HE 52 is called multiplicative; and f(G) <f(H) w h enever G is a subgraph of H is called increasing. The classification of multiplicative increasing graph functions is still open. Up to now, there are a lot of known multiplicative increasing graph functions. In this paper, we introduce a new class of multiplicative increasing graph functions, namely, ~)o,~ for all G E % and 0 # S E V(G), defined to be the number of all possible homomorphic images of S for the homomorphism from G into H. Several properties of additive multiplicative increasing graph functions are also discussed in this paper.

📜 SIMILAR VOLUMES

Independence and graph homomorphisms gra

Independence and graph homomorphisms graph homomorphisms

✍ Michael O. Albertson; Lily Chan; Ruth Haas 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 305 KB

## Abstract 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 (3__n__)/7 vertices. This is best possible. The proof proceeds by producing a homomorphism to the 7‐cycle and invoking the No Homomorphism

Homomorphism–homogeneous graphs

✍ Momchil Rusinov; Pascal Schweitzer 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 141 KB

## Abstract We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–

Geometric graph homomorphisms

✍ Debra L. Boutin; Sally Cockburn 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB

## Abstract A __geometric graph__ is a simple graph drawn on points in the plane, in general position, with straightline edges. A __geometric__ __homomorphism__ from to is a vertex map that preserves adjacencies and crossings. This work proves some basic properties of geometric homomorphisms and

Homomorphically full graphs

✍ Richard Brewster; Gary MacGillivray 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 662 KB

Inequalities with respect to graph homom

Inequalities with respect to graph homomorphism

✍ Huishan Zhou 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 184 KB

If there is a homomorphism from a graph G onto a graph H, then there exist some inequalities relating 'the degree ratio' of the two graphs which have some interesting corollaries.

Extremal graphs for homomorphisms

✍ Jonathan Cutler; A. J. Radcliffe 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed imag