✦ LIBER ✦

Algorithms for constructing graphs and digraphs with given valences and factors

✍ Scribed by D.J. Kleitman; D.L. Wang

Publisher: Elsevier Science
Year: 1973
Tongue: English
Weight: 942 KB
Volume: 6
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(73)90037-x

No coin nor oath required. For personal study only.

✦ Synopsis

Given a set of valences ( ui) such that { ui> and (vi-k} are both realizable as valences of graphs without loops or multiple edges, an explicit conslruction method is described for obtaining a graph with valences {ui] having a k-factor. A number of extensions of the result are obtained. Similar results are obtained for directed graphs.

📜 SIMILAR VOLUMES

Graphs and digraphs with given girth and

Graphs and digraphs with given girth and connectivity

✍ Jiping Liu; ; Huishan Zhou 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 230 KB

In this paper, we show that for any given two positive integers g and k with g > 3, there exists a graph (digraph) G with girth g and connectivity k. Applying this result, we give a negative answer to the problem proposed by M. Junger, G. Reinelt and W.R Pulleyblank (1985).

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

Efficient and Constructive Algorithms fo

Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs

✍ Hans L. Bodlaender; Ton Kloks 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 373 KB

In this paper we give, for all constants k, l, explicit algorithms that, given a graph Ž . Gs V,E with a tree-decomposition of G with treewidth at most l, decide Ž . whether the treewidth or pathwidth of G is at most k, and, if so, find a Ž . tree-decomposition or path-decomposition of G of width at

An optimal algorithm for constructing or

An optimal algorithm for constructing oriented voronoi diagrams and geographic neighborhood graphs

✍ Maw Shang Chang; Nen-Fu Huang; Chuan-Yi Tang 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 442 KB

An algorithm for construction of a k-con

An algorithm for construction of a k-connected graph with minimum number of edges and quasiminimal diameter

✍ Ulrich Schumacher 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 470 KB

Two fundamental considerations in the design of a communication network are reliability and maximum transmission delay. In this paper we give an algorithm for construction of an undirected graph with n vertices in which there are k node-disjoint paths between any two nodes. The generated graphs will

An intermediate value theorem for graphs

An intermediate value theorem for graphs with given automorphism group

✍ Pavol Hell; Louis V. Quintas 📂 Article 📅 1979 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB

## Abstract For a positive integer __n__ and a finite group __G__, let the symbols __e__(__G, n__) and __E__(__G, n__) denote, respectively, the smallest and the greatest number of lines among all __n__‐point graphs with automorphism group __G__. We say that the Intermediate Value Theorem (IVT) hol