✦ LIBER ✦

On a multiplicative graph function conjecture

✍ Scribed by Lih-Hsing Hsu

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 802 KB
Volume: 45
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(83)90041-9

No coin nor oath required. For personal study only.

✦ Synopsis

For any graph H, the function h,. defined by setting h,(G) equal to the number of homomorphisms from G into H, is a multiplicative increasing function. L.ov&sz [2] has asked whether ail nonzero multiplicative increasing functions are generated by functions of this type. We show that this is not the case. I-iowever, the classification of multiplicative increasing aaph fUllCtionS iS Still unsolved. we prove several properties of such functions in this pqK?r. Let G =(X, E) is called a graph if X is a finite set and E is a subset of ((a, b) 1 a# b, (a, b) is an unordered pair of X}. We say X = V(G) is the vertex set of G, E= E(G) is the edge set of G. Let G = (X, E), H = (Y, F) be two graphs. The product of G and Z-Z is the graph G x If = (Z, K), where 2 = XX Y, the Cartesian product of X and Y, and K = {((x,9 YI), (x*9 Yz)) I t xl, X~)E E and (y,, Y*)E F}. We let Gh denote G x G x -* . X G (k times); the sum of G and H is the graph G + Z-Z = ( W, U) with W=X,WY,, u=E,UF, where G'=(X,,E,)=G, H,==(Y,,F,)=H and X,rlY,=p). Amap 4:Y ---, X is called a homomorphism if it satisfies (y , , y2) E F itnplies (Il(yt), +C(YZ)) E E.

📜 SIMILAR VOLUMES

On a harmonious graph conjecture

✍ Eugene Levine 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 125 KB

Let K~ ) be the umon of two complete graphs on n vertices which have preosely one vertex in common. Graham and Sloane have shown that K~ ~ is not harmomous for n od:~, /(~,~ is harmonious, and K~62~ is not harmonious. They also conjecture that K~' t,, not h,~rmomous except for n = 4. Here, it Is sho

On the critical graph conjecture

✍ Hian Poh Yap 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 222 KB

## Abstract Gol'dberg has recently constructed an infinite family of 3‐critical graphs of even order. We now prove that if there exists a __p__(≥4)‐critical graph __K__ of odd order such that __K__ has a vertex __u__ of valency 2 and another vertex __v__ ≠ __u__ of valency ≤(__p__ + 2)/2, then ther

On the strong perfect graph conjecture

✍ Stephan Olariu 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

A graph G is perfect if for every induced subgraph H of G the chromatic number x(H) equals the largest number w ( H ) of pairwise adjacent vertices in H. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement C contains an odd cho

Remarks on the critical graph conjecture

✍ I. Broere; C.M. Mynhardt 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 344 KB

The vertex-critical graph conjecture (critical graph conjecture respectively) states that every vertex-critical (critical) graph has an odd number of vertices. In this note we prove that if G is a critical graph of even order, then G has at least three vertices of less-than-maximum valency. In addit

Extending a function on a graph

✍ D.F. Robinson 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 913 KB

Let G be a graph with vertex set V, and let h be a function mapping a subset U of I/ into the real numbers R. If f is a function from I' to R, we define S y) to be the sum of If(b)f(a)1 over all edges {a, b} of G. A best extension of h is such a function f with f(x) = h(x) for x E U and minimum 6 u

A class of additive multiplicative graph

A class of additive multiplicative graph functions

✍ Lih-Hsing Hsu; Chiuyuan Chen; En-Yih Jean 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 650 KB

For a fixed graph G, the capacity function for G, Po, is defined by Pc(H)= lim,\_\_,®[yo(H')] TM, where y6(H) is the maximum number of disjoint G's in H. In , Hsu proved that Pr2 can be viewed as a lower bound for multiplicative increasing graph functions. But it was not known whether Pr2 is multipl