𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The solution to an extremal problem on balanced extensions of graphs

✍ Scribed by A. Ruciński; A. Vince

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
694 KB
Volume
17
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

For n sufficiently large the order of a smallest balanced extension of a graph of order n is, in the worst case, ⌊(n + 3)^2^/8⌋. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

NP completeness of the edge precoloring
NP completeness of the edge precoloring extension problem on bipartite graphs
✍ Jiří Fiala 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 63 KB 👁 1 views

## Abstract We show that the following problem is __NP__ complete: Let __G__ be a cubic bipartite graph and __f__ be a precoloring of a subset of edges of __G__ using at most three colors. Can __f__ be extended to a proper edge 3‐coloring of the entire graph __G__? This result provides a natural co

The Solution of a Problem of Godsil on C
The Solution of a Problem of Godsil on Cubic Cayley Graphs
✍ Cai Heng Li 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 267 KB

In this short paper, we give a positive answer to a question of C. D. Godsil (1983, Europ. J. Combin. 4, 25 32) regarding automorphisms of cubic Cayley graphs of 2-groups: ``If Cay(G, S) is a cubic Cayley graph of a 2-group G and A=Aut Cay(G, S), does A 1 {1 imply Aut(G, S){1?'' 1998 Academic Press

On quadrilaterals in layers of the cube
On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs
✍ Schelp, Richard H.; Thomason, Andrew 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB 👁 2 views

Erdős has conjectured that every subgraph of the n-cube Q n having more than (1/2+o(1))e(Q n ) edges will contain a 4-cycle. In this note we consider 'layer' graphs, namely, subgraphs of the cube spanned by the subsets of sizes k -1, k and k + 1, where we are thinking of the vertices of Q n as being