✦ LIBER ✦

On a harmonious graph conjecture

✍ Scribed by Eugene Levine

Publisher: Elsevier Science
Year: 1983
Tongue: English
Weight: 125 KB
Volume: 46
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(83)90277-7

No coin nor oath required. For personal study only.

✦ Synopsis

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 shown that if K~ 2~ ts harmomous, then n must be a sum of two squares.

📜 SIMILAR VOLUMES

On the harmonious chromatic number of a

On the harmonious chromatic number of a graph

✍ John Mitchem 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 755 KB

The harmonious chromatic number of a graph G, denoted by h(G), is the least number of colon which can be assigned to the vertices of G such that adjacent vertices are colored differently and any two distinct edges have different color pairs. This is a slight variation of a definition given independe

On a multiplicative graph function conje

On a multiplicative graph function conjecture

✍ Lih-Hsing Hsu 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 802 KB

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

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

On an upper bound for the harmonious chr

On an upper bound for the harmonious chromatic number of a graph

✍ Zhikang Lu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.