✦ LIBER ✦

On the number of irreducible coverings by edges of complete bipartite graphs

✍ Scribed by Ioan Tomescu

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 102 KB
Volume: 150
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(96)81420-8

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper it is proved that the exponential generating function of the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite graphs Kp.q equals exp(xe r + ye x -x -y -xy) -t.

📜 SIMILAR VOLUMES

The generating function of irreducible c

The generating function of irreducible coverings by edges of complete k-partite graphs

✍ Virgil Domocos; Ş.N. Buzeţeanu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 208 KB

A generalization of a recent result of Tomescu ( 1993) is presented. The method is purely combinatorial and is based on the theory of species of several variables.

The maximal number of induced complete b

The maximal number of induced complete bipartite graphs

✍ Béla Bollobás; Chiê Nara; Shun-ichi Tachibana 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 230 KB

The aim of this paper is to determine the maximal number of induced K(t, t) subgraphs in graphs of given order and in graphs of given size. Given a graph G and a natural number t, denote by ft(G) the number of induced subgraphs of G isomorphic to K(t, t). Our notation is that of ; in particular, K(

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 size Ramsey number of a complete bip

The size Ramsey number of a complete bipartite graph

✍ P. Erdo˝s; C.C. Rousseau 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 240 KB

Erd6s. P. and C.C. Rousseau, The size Ramsey number of a complete bipartite graph, Discrete Mathematics 113 (1993) 259-262. In this note we prove that the (diagonal) size Ramsey number of K,,.,, is bounded below by $2'2".

s-Regular cubic graphs as coverings of t

s-Regular cubic graphs as coverings of the complete bipartite graph K3,3

✍ Yan-Quan Feng; Jin Ho Kwak 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

## Abstract A graph is __s‐regular__ if its automorphism group acts freely and transitively on the set of __s__‐arcs. An infinite family of cubic 1‐regular graphs was constructed in [10], as cyclic coverings of the three‐dimensional Hypercube. In this paper, we classify the __s__‐regular cyclic cov

On the Pagenumber of Complete Bipartite

On the Pagenumber of Complete Bipartite Graphs

✍ Hikoe Enomoto; Tomoki Nakamigawa; Katsuhiro Ota 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 324 KB

The pagenumber p(G) of a graph G is defined as the smallest n such that G can be embedded in a book with n pages. We give an upper bound for the pagenumber of the complete bipartite graph K m, n . Among other things, we prove p(K n, n ) w2nÂ3x+1 and p(K wn 2 Â4x, n ) n&1. We also give an asymptotic