✦ LIBER ✦

The maximal number of induced complete bipartite graphs

✍ Scribed by Béla Bollobás; Chiê Nara; Shun-ichi Tachibana

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 230 KB
Volume: 62
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90214-1

No coin nor oath required. For personal study only.

✦ Synopsis

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(t, t) is a complete bipartite graph with t vertices in each class and TE(n) is a complete bipartite graph with L½nJ and [½n] vertices in the classes. For given values 4 ~< 2t ~< n and 2 <~ t ~< s we shall determine max/oft(G): IGI = n) and max,(G): e(G)=s2}. Results in a similar vein were proved by ErdSs and

📜 SIMILAR VOLUMES

On the number of maximal bipartite subgr

On the number of maximal bipartite subgraphs of a graph

✍ Jesper Makholm Byskov; Bolette Ammitzbøll Madsen; Bjarke Skjernaa 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

We show new lower and upper bounds on the maximum number of maximal induced bipartite subgraphs of graphs with n vertices. We present an infinite family of graphs having 105 n=10 % 1:5926 n ; such subgraphs show an upper bound of O(12 n=4 ) ¼ O(1:8613 n ) and give an algorithm that finds all maximal

More rotation numbers for complete bipar

More rotation numbers for complete bipartite graphs

✍ Béla Bollobás; E. J. Cockayne 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB

## Abstract Let __G__ be a simple undirected graph which has __p__ vertices and is rooted at __x__. Informally, the __rotation number h(G, x)__ of this rooted graph is the minimum number of edges in a __p__ vertex graph __H__ such that for each vertex __v__ of __H__, there exists a copy of __G__ in

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".

Pagenumber of complete bipartite graphs

✍ Douglas J. Muder; Margaret Lefevre Weaver; Douglas B. West 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 929 KB

On the number of irreducible coverings b

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

✍ Ioan Tomescu 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 102 KB

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.

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