Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

The maximal number of inducedr-partite subgraphs

In this paper, we extend earlier results concerning the maximal number of induced completer-partite graphs in a graphG of ordern. In particular, we show that ift > 1 + logr, then the maximal number of inducedK _r (t)'s is achieved in the case of the Turán graphT _r (n), and that this bound ont is essentially best possible.     

Isoperimetric numbers of graph bundles

The main aim of this paper is to give some upper and lower bounds for the isoperimetric numbers of graph coverings or graph bundles, with exact values in some special cases. In addition, we show that the isoperimetric number of any covering graph is not greater than that of the base graph. Mohar's theorem for the isoperimetric number of the cartesian product of a graph and a complete graph can be extended to a more general case: The isoperimetric numberi(G × K _2n) of the cartesian product of any graphG and a complete graphK _2n on even vertices is the minimum of the isoperimetric numberi(G) andn, and it is also a sharp lower bound of the isoperimetric numbers of all graph bundles over the graphG with fiberK _2n. Furthermore, ifn 2i(G) then the isoperimetric number of any graph bundle overG with fibreK _n is equal to the isoperimetric numberi(G) ofG. Partially supported by The Ministry of Education, Korea.     

Bounds of eigenvalues of a graph

LetG be a simple graph withn vertices. We denote by _i(G) thei-th largest eigenvalue ofG. In this paper, several results are presented concerning bounds on the eigenvalues ofG. In particular, it is shown that –1₂(G)(n–2)/2, and the left hand equality holds if and only ifG is a complete graph with at least two vertices; the right hand equality holds if and only ifn is even andG2K _n/2.     

On the number of edge disjoint cliques in graphs of given size

In this paper, we prove that any graph ofn vertices andt _r–1(n)+m edges, wheret _r–1(n) is the Turán number, contains (1–o(1)m edge disjointK _r'sifm=o(n ²). Furthermore, we determine the maximumm such that every graph ofn vertices andt _r–1(n)+m edges containsm edge disjointK _r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812.     

Subdivisions of Transitive Tournaments

We prove that, for r ≥ 2 andn ≥ n(r), every directed graph with n vertices and more edges than the r -partite Turán graph T(r, n) contains a subdivision of the transitive tournament on r + 1 vertices. Furthermore, the extremal graphs are the orientations ofT (r, n) induced by orderings of the vertex classes.     

Eigenvalues of the adjacency matrix of tetrahedral graphs

A tetrahedral graph is defined to be a graphG, whose vertices are identified with the unordered triplets onn symbols, such that vertices are adjacent if and only if the corresponding triplets have two symbols in common. Ifn ₂ (x) denotes the number of verticesy, which are at distance 2 fromx andA(G) denotes the adjacency matrix ofG, thenG has the following properties: P₁) the number of vertices is . P₂)G is connected and regular. P₃)n ₂ (x) = 3/2(n–3)(n–4) for allx inG. P₄) the distinct eigenvalues ofA(G) are –3, 2n–9,n–7, 3(n–3). We show that, ifn > 16, then any graphG (with no loops and multiple edges) having the properties P₁)–P₄) must be a tetrahedral graph. An alternative characterization of tetrahedral graphs has been given by the authors in [1].This research was supported by the National Science Foundation Grant No. GP-5790, and the Army Research Office (Durham) Grant No. DA-ARO-D-31-12-G910. (Institute of Statistics Mimeo Series No. 571, March 1968.)     

Panconnected graphs II

A graphG of orderp is said to bepanconnected if for each pairu, v of vertices ofG, there exists a,u, v-path of lengthl inG, for eachl such that d_G(u, v)lp – 1, whered _G (u, v) denotes the length of a shortestu, v-path inG. Three conditions are shown to be sufficient for a graphG of orderp to be panconnected: (1) the degree of each vertex ofG is at least (p+2)/2; (2) the sum of the degrees of each pair of nonadjacent vertices ofG is at least (3p–2)/2; (3) the graphG has at least edges. It is also shown that each of these conditions is best possible. Additional results on panconnectedness are obtained including a characterization of those completen-partite graphs which are panconnected.     

A note on 1-factors in graphs

Conditions on a graphG are presented which are sufficient to guarantee thatG–Z contains a 1-factor, whereZ is a set of edges ofG of restricted cardinality. These conditions provide generalizations of several known results and, further, establish the result that ifG is anr-regular, (r–2)-edge-connected graph (r2) of even order andz is an integer with 0zr–1 such thatG contains fewer thanr–z edge cut sets of cardinalityr–2, thenG–Z has a 1-factor for each setZ ofz edges ofG.     

Computation of a lower bound of the lengths of schedules

For a graphG of strict partial ordering, the lower estimates T₁ T₂T₃T₄ of the lengths of m-processor schedules are given depending on the extent of the details known about graphG. The best estimate, T₄, is obtained if the partitions of the set of vertices ofG into levels from above and from below are known. The complexity of obtaining the estimate T₄ is equal to O(n), where n=G.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 124, pp. 35–40, 1983.     

Triple placement of graphs

A graphG of ordern is said to be 3-placeable if there are three edge disjoint copies ofG inK _n. In the paper we prove that every graph of ordern and size at mostn–2 is 3-placeable unless isomorphic either toK ₃ 2K ₁ or toK ₄ 4K ₁.     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.     

On thel-connectivity of a graph

For an integerl 2, thel-connectivity of a graphG is the minimum number of vertices whose removal fromG produces a disconnected graph with at leastl components or a graph with fewer thanl vertices. A graphG is (n, l)-connected if itsl-connectivity is at leastn. Several sufficient conditions for a graph to be (n, l)-connected are established. IfS is a set ofl( 3) vertices of a graphG, then anS-path ofG is a path between distinct vertices ofS that contains no other vertices ofS. TwoS-paths are said to be internally disjoint if they have no vertices in common, except possibly end-vertices. For a given setS ofl 2 vertices of a graphG, a sufficient condition forG to contain at leastn internally disjointS-paths, each of length at most 2, is established.     

Cycles in weighted graphs

A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4].     

Greatest common subgraphs with specified properties

A graphG without isolated vertices is a greatest common subgraph of a setG of graphs, all having the same size, ifG is a graph of maximum size that is isomorphic to a subgraph of every graph inG. A number of results concerning greatest common subgraphs are presented. For several graphical propertiesP, we discuss the problem of determining, for a given graphG with propertyP, the existence of two non-isomorphic graphsG ₁ andG ₂ of equal size, also with propertyP, such thatG is the unique greatest common subgraph ofG ₁ andG ₂. In particular, this problem is solved whenP is the property of being 2-connected and whenP is the property of having chromatic numbern.     

A new recursive theorem onn-extendibility

A graphG having a 1-factor is calledn-extendible if every matching of sizen extends to a 1-factor. LetG be a 2-connected graph of order 2p. Letr0 andn>0 be integers such thatp–rn+1. It is shown that ifG/S isn-extendible for every connected subgraphS of order 2r for whichG/S is connected, thenG isn-extendible.     

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

Recently much attention has been focused on the theory of quasi-random graph and hypergraph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. We shall investigate propertiesP which do not imply quasi-randomnes for sequences (G _n ) of graphs on their own, but do imply if they hold not only for the whole graphG _n but also for every sufficiently large subgraph ofG _n . Here the properties are strongly connected to countingnot necessarily induced subgraphs of a given type, while in a subsequent paper we shall investigate the properties connected with counting induced subgraphs.Dedicated to the memory of Paul ErdsResearch supported by OTKA N1909.     

Graphs of diameter 3 with the minimum number of edges

The graphG is called a porcupine, ifGA is a complete graph for some setA, every other vertex has degree one, and its only edge is joined toA. In this paper a conjecture of Bollobás is settled almost completely. Namely, it is proved that ifG is a graph onn vertices of diameter 3 with maximum degreeD, D > 2.31 ,D (n – 1)/2 and it has the mimimum number of edges, then it is a porcupine.This paper was written while the author visited the Departments of Mathematics, Tel-Aviv University, whose hospitality is gratefully acknowledged.     

Embedding (p,p−1) graphs in their complements

A graphG is embeddable in its complement ifG is isomorphic with a subgraph of . A complete characterization is given of those (p,p−1) graphs which are embeddable in their complements. In particular, letG be a (p,p−1) graph wherep≧6 ifp is even andp≧9 ifp is odd; thenG is embeddable in if and only ifG is neither the starK _1,p−1 norK _1,n ∪C ₃ withn≧4.     

A relationship between bounds on the sum of squares of degrees of a graph

LetG = (V, E) be a simple graph withn vertices and e edges. Letdi be the degree of the ith vertex v_i ∈ V andm _i the average of the degrees of the vertices adjacent to vertexv _i ∈ V. It is known by Caen [1] and Das [2] that $\frac{{4e^2 }}{n} \leqslant d_1^2 + ... + d_n^2 \leqslant e max \{ d_j + m_j |v_j \in V\} \leqslant e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ . In general, the equalities do not hold in above inequality. It is shown that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 $ . In fact, it is shown a little bit more strong result that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} $ . For a graphG withn < 2 vertices, it is shown that G is a complete graphK _n if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} = e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ .