✦ LIBER ✦

Graphs with given odd sets

✍ Scribed by Chen, Guantao; Schelp, Richard H.; ?olt�s, ?ubom�r

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 123 KB
Volume: 24
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199701)24:1<69::aid-jgt8>3.0.co;2-h

No coin nor oath required. For personal study only.

✦ Synopsis

Given a graph G, its odd set is a set of all integers k such that G has odd number of vertices of degree k. We show that if two graphs G and H of the same order have the same odd sets then they can be obtained from each other by succesive application of the following two operations:

• add or remove an edge joining two vertices of the same degree • replace two independent edges with two new independent edges on the same vertex set.

If, moreover, both graphs G and H are regular or both are forests, it is sufficient to use only the first operation, but, in general, both operations are necessary.

📜 SIMILAR VOLUMES

Graphs with given odd sets and the least

Graphs with given odd sets and the least number of vertices

✍ Louis Hakimi, S. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 2 views

This note presents a solution to the following problem posed by Chen, Schelp, and Soltés: find a simple graph with the least number of vertices for which only the degrees of the vertices that appear an odd number of times are given.

The maximum valency of regular graphs wi

The maximum valency of regular graphs with given order and odd girth

✍ Guo-Hui Zhang 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 294 KB 👁 1 views

## Abstract The odd girth of a graph __G__ is the length of a shortest odd cycle in __G__. Let __d__(__n, g__) denote the largest __k__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g__. It is shown that __d____n, g__ ≥ 2|__n__/__g__≥ if __n__ ≥ 2__g__. As a consequenc

Graphs with given connectivity propertie

Graphs with given connectivity properties

✍ Lawrencenko, Serge; Luo, Qiang 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB

A node of a graph G, thought of as representing a communication network, is said to be redundant provided that its removal does not diminish the connectivity. In constructing networks, we require reliable connectedness in addition to the usual requirement of reliability (i.e., the higher the connect

Graphs with given group and given consta

Graphs with given group and given constant link

✍ Walter Vogler 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 228 KB

## Abstract __A__ graph __L__ is called a link graph if there is a graph __G__ such that for each vertex of __G__ its neighbors induce a subgraph isomorphic to __L.__ Such a G is said to have constant link __.__L Sabidussi proved that for any finite group F and any __n__ ⩾ 3 there are infinitely ma

Regular graphs with given girth pair

✍ Frank Harary; Peter Kovács 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 453 KB 👁 1 views

## Abstract The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair is proved and simple bounds for their smallest order are developed. Several infinite classes of such graphs are constructed and it is

Smallest regular graphs with prescribed

Smallest regular graphs with prescribed odd girth

✍ Guo-Hui Zhang 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 484 KB 👁 1 views

## Abstract The odd girth of a graph __G__ gives the length of a shortest odd cycle in __G.__ Let __f(k,g)__ denote the smallest __n__ such that there exists a __k__‐regular graph of order __n__ and odd girth __g.__ The exact values of __f(k,g)__ are determined if one of the following holds: __k__