Expanding graphs contain all small trees

The assertion of the title is formulated and proved. The result is then used to construct graphs with a linear number of edges that, even after the deletion of almost all of their edges or almost all of their vertices, continue to contain all small trees.     

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.     

Explicit construction of regular graphs without small cycles

For every integerd>2 we give an explicit construction of infinitely many Cayley graphsX of degreed withn(X) vertices and girth >0.4801...(logn(X))/log (d−1)−2. This improves a result of Margulis. Dedicated to Paul Erdős on his seventieth birthday     

Hamiltonian cycles in bipartite graphs

We give a sufficient condition for bipartite graphs to be Hamiltonian. The condition involves the edge-density and balanced independence number of a bipartite graph.     

On bicyclic graphs with maximal energy

Let λ₁,λ₂,…,λ_n be the eigenvalues of a graph G of order n. The energy of G is defined as E(G)=|λ₁|+|λ₂|+?+|λ_n|. Let be the graph obtained from two copies of C₆ joined by a path P_n-10, B_n be the class of all bipartite bicyclic graphs that are not the graph obtained from two cycles C_a and C_b (a,b?10 and a≡b≡2 (mod 4)) joined by an edge. In this paper, we show that is the graph with maximal energy in B_n, which gives a partial solution to Gutman’s conjecture in Gutman and Vidovi? (2001) [I. Gutman, D. Vidovi?, Quest for molecular graphs with maximal energy: a computer experiment, J. Chem. Inf. Sci. 41 (2001) 1002-1005].     

Spectral radius of graphs with given matching number

In this paper, we show that of all graphs of order n with matching number β, the graphs with maximal spectral radius are K_n if n = 2β or 2β + 1; if 2β + 2 ? n < 3β + 2; or if n = 3β + 2; if n > 3β + 2, where is the empty graph on t vertices.     

Cubic Ramanujan graphs

A fimily of cubic Ramanujan graph is explicitly constructed. They are realized as Cayley graphs of a certain free group acting on the 3-regular tree; this group is obtained from a definite quaternion algebra that splits at the prime 2 and has a maximal order of class number 1.     

On the index of tricyclic graphs with perfect matchings

Let T(2k) be the set of all tricyclic graphs on 2k(k?2) vertices with perfect matchings. In this paper, we discuss some properties of the connected graphs with perfect matchings, and then determine graphs with the largest index in T(2k).     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

Supersaturated graphs and hypergraphs

We shall consider graphs (hypergraphs) without loops and multiple edges. Let ? be a family of so called prohibited graphs and ex (n, ?) denote the maximum number of edges (hyperedges) a graph (hypergraph) onn vertices can have without containing subgraphs from ?. A graph (hyper-graph) will be called supersaturated if it has more edges than ex (n, ?). IfG hasn vertices and ex (n, ?)+k edges (hyperedges), then it always contains prohibited subgraphs. The basic question investigated here is: At least how many copies ofL ε ? must occur in a graphG ⁿ onn vertices with ex (n, ?)+k edges (hyperedges)?     

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

Unicyclic graphs with large energy

We study the energy (i.e., the sum of the absolute values of all eigenvalues) of so-called tadpole graphs, which are obtained by joining a vertex of a cycle to one of the ends of a path. By means of the Coulson integral formula and careful estimation of the resulting integrals, we prove two conjectures on the largest and second-largest energy of a unicyclic graph due to Caporossi, Cvetkovi?, Gutman and Hansen and Gutman, Furtula and Hua, respectively. Moreover, we characterise the non-bipartite unicyclic graphs whose energy is largest.     

Regular subgraphs of dense graphs

Every graph onn vertices, with at leastc _k n logn edges contains ak-regular subgraph. This answers a question of Erdős and Sauer.     

4-regular claw-free IM-extendable graphs

A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K_1,3. The kth power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are , and T_r, r?2, where T_r is the graph with 4r vertices u_i,v_i,x_i,y_i, 1?i?r, such that for each i with 1?i?r, {u_i,v_i,x_i,y_i} is a clique of T_r and . We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K₄×K₂, and .     

The cover pebbling number of graphs

A pebbling move on a graph consists of taking two pebbles off of one vertex and placing one pebble on an adjacent vertex. In the traditional pebbling problem we try to reach a specified vertex of the graph by a sequence of pebbling moves. In this paper we investigate the case when every vertex of the graph must end up with at least one pebble after a series of pebbling moves. The cover pebbling number of a graph is the minimum number of pebbles such that however the pebbles are initially placed on the vertices of the graph we can eventually put a pebble on every vertex simultaneously. We find the cover pebbling numbers of trees and some other graphs. We also consider the more general problem where (possibly different) given numbers of pebbles are required for the vertices.     

Extremal clique coverings of complementary graphs

Letcc(G) (resp. cp(G)) be the least number of complete subgraphs needed to cover (resp. partition) the edges of a graphG. We present bounds on max {cc(G)+cc(Ḡ)}, max {cp(G)+cp(Ḡ)}, max {cc(G)cc(Ḡ)} and max {cp(G)cp(Ḡ)} where the maxima are taken over all graphsG onn vertices and Ḡ is the complement ofG inK _n . Several related open problems are also given.     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.