Bounds on the eigenvalues of graphs with cut vertices or edges

In this paper, we characterize the extremal graph having the maximal Laplacian spectral radius among the connected bipartite graphs with n vertices and k cut vertices, and describe the extremal graph having the minimal least eigenvalue of the adjacency matrices of all the connected graphs with n vertices and k cut edges. We also present lower bounds on the least eigenvalue in terms of the number of cut vertices or cut edges and upper bounds on the Laplacian spectral radius in terms of the number of cut vertices.     

Triangle-free partial graphs and edge covering theorems

In section 1 some lower bounds are given for the maximal number of edges ofa (p ? 1)- colorable partial graph. Among others we show that a graph on n vertices with m edges has a (p?1)-colorable partial graph with at least mT_n.p/(ⁿ₂) edges, where T_n.p denotes the so called Turán number. These results are used to obtain upper bounds for special edge covering numbers of graphs. In Section 2 we prove the following theorem: If G is a simple graph and μ is the maximal cardinality of a triangle-free edge set of G, then the edges of G can be covered by μ triangles and edges. In Section 3 related questions are examined.     

Lower-bounds on the connectivities of a graph

This article presents a study of the connectivities of a graph as a function of other graph parameters such as the number of vertices, the maximum degree, and the diameter. As a result, lower-bounds on the connectivities of a graph as a function of these parameters are computed. These bounds could serve as sufficient conditions for a graph to be h-edge-connected or k-connected. Consequently, the connectivity characteristics of many of the densest known graphs are determined.     

Minimal separating sets of maximum size

A connected graph G can be disconnected or reduced to a single vertex by removing an appropriate subset of the vertex set V(G), and can be disconnected by removing a suitable subset of the edge set E(G). Attention has usually been centered on separating sets having minimum cardinality, and parameters called the vertex connectivity and the edge connectivity defined. These classical concepts are generalized by using separating sets which are minimal. By considering the maximum as well as the minimum cardinality of such sets, one defines vertex and edge connectivity parameters. Sharp upper bounds are established for these numbers and their values computed for certain classes of graphs. An analogue of Whitney's theorem on connectivity is obtained. Parameters are also defined for minimal separating sets consisting of a mixture of vertices and edges, and these are shown to depend on the maximum and minimum values of the vertex and edge connectivity parameters.     

Rainbow Connection and Graph Products

A path in an edge colored graph G is called a rainbow path if all its edges have pairwise different colors. Then G is rainbow connected if there exists a rainbow path between every pair of vertices of G and the least number of colors needed to obtain a rainbow connected graph is the rainbow connection number. If we demand that there must exist a shortest rainbow path between every pair of vertices, we speak about strongly rainbow connected graph and the strong rainbow connection number. In this paper we study the (strong) rainbow connection number on the direct, strong, and lexicographic product and present several upper bounds for these products that are attained by many graphs. Several exact results are also obtained.     

Sharp upper bounds for the adjacency and the signless Laplacian spectral radius of graphs

Let G be a simple graph with n vertices and m edges. In this paper, we present some new upper bounds for the adjacency and the signless Laplacian spectral radius of graphs in which every pair of adjacent vertices has at least one common adjacent vertex. Our results improve some known upper bounds. The main tool we use here is the Lagrange identity.     

On least eigenvalues and least eigenvectors of real symmetric matrices and graphs

We give an upper bound for the least eigenvalue of a principal submatrix of a real symmetric matrix with zero diagonal, from which we establish an upper bound for the least eigenvalue of a graph when some vertices are removed using the components of the least eigenvector(s). We give lower and upper bounds for the least eigenvalue of a graph when some edges are removed. We also establish bounds for the components of the least eigenvector(s) of a real symmetric matrix and a graph.     

On the maximum number of edges in quasi-planar graphs

A topological graph is quasi-planar, if it does not contain three pairwise crossing edges. Agarwal et al. [P.K. Agarwal, B. Aronov, J. Pach, R. Pollack, M. Sharir, Quasi-planar graphs have a linear number of edges, Combinatorica 17 (1) (1997) 1-9] proved that these graphs have a linear number of edges. We give a simple proof for this fact that yields the better upper bound of 8n edges for n vertices. Our best construction with 7n−O(1) edges comes very close to this bound. Moreover, we show matching upper and lower bounds for several relaxations and restrictions of this problem. In particular, we show that the maximum number of edges of a simple quasi-planar topological graph (i.e., every pair of edges have at most one point in common) is 6.5n−O(1), thereby exhibiting that non-simple quasi-planar graphs may have many more edges than simple ones.     

Upper and lower bounds for the energy of bipartite graphs

Using Lagrange's multiplier rule, we find upper and lower bounds of the energy of a bipartite graph G, in terms of the number of vertices, edges and the spectral moment of fourth order. Moreover, the upper bound is attained in a graph G if and only if G is the graph of a symmetric balanced incomplete block design (BIBD). Also, we determine the graphs for which the lower bound is sharp.     

On unavoidable graphs

How many edges can be in a graph which is forced to be contained in every graph onn vertices ande edges? In this paper we obtain bounds which are in many cases asymptotically best possible.     

On the Number of Edges in Colour-Critical Graphs and Hypergraphs

A (hyper)graph G is called k-critical if it has chromatic number k, but every proper sub(hyper)graph of it is (k-1)-colourable. We prove that for sufficiently large k, every k-critical triangle-free graph on n vertices has at least (k-o(k))n edges. Furthermore, we show that every (k+1)-critical hypergraph on n vertices and without graph edges has at least (k-3/³?{k}) n(k-3/\sqrt[3]{k}) n edges. Both bounds differ from the best possible bounds by o(kn) even for graphs or hypergraphs of arbitrary girth.     

The number of spanning trees of a graph

In this paper, we present some sharp upper bounds for the number of spanning trees of a connected graph in terms of its structural parameters such as the number of vertices, the number of edges, maximum vertex degree, minimum vertex degree, connectivity and chromatic number.     

Connectivity measures in matched sum graphs

A matched sum graph G of two graphs G₁ and G₂ of the same order is obtained from the union of G₁ and G₂ and from joining each vertex of G₁ with one vertex of G₂ according to one bijection f between the vertices in V(G₁) and V(G₂). When G₁=G₂=H then f is just a permutation of V(H) and the corresponding matched sum graph is a permutation graph H^f. In this paper, we derive lower bounds for the connectivity, edge-connectivity, and different conditional connectivities in matched sum graphs, and present sufficient conditions which guarantee maximum values for these conditional connectivities.     

An exact algorithm for subgraph homeomorphism

The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given in the input instance is termed fixed-vertex subgraph homeomorphism.We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time 2^n−pn^O(1) or in time 3^n−pn^O(1) and polynomial space. In effect, we obtain new non-trivial upper bounds on the time complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.     

Geometric Graphs with Few Disjoint Edges

A geometric graph is a graph drawn in the plane so that the vertices are represented by points in general position, the edges are represented by straight line segments connecting the corresponding points. Improving a result of Pach and T?rőcsik, we show that a geometric graph on n vertices with no k+1 pairwise disjoint edges has at most k ³ (n+1) edges. On the other hand, we construct geometric graphs with n vertices and approximately (3/2)(k-1)n edges, containing no k+1 pairwise disjoint edges. We also improve both the lower and upper bounds of Goddard, Katchalski, and Kleitman on the maximum number of edges in a geometric graph with no four pairwise disjoint edges. Received May 7, 1998, and in revised form March 24, 1999.     

Broadcasting from multiple originators

We begin an investigation of broadcasting from multiple originators, a variant of broadcasting in which any k vertices may be the originators of a message in a network of n vertices. The requirement is that the message be distributed to all n vertices in minimum time. A minimumk-originator broadcast graph is a graph on n vertices with the fewest edges such that any subset of k vertices can broadcast in minimum time. B_k(n) is the number of edges in such a graph. In this paper, we present asymptotic upper and lower bounds on B_k(n). We also present an exact result for the case when . We also give an upper bound on the number of edges in a relaxed version of this problem in which one additional time unit is allowed for the broadcast.     

The extremal graph problem of the icosahedron

P. Turán has asked the following question:Let I¹² be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gⁿ of n vertices if Gⁿ does not contain I¹² as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I¹². This graph Hⁿ can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [$\text{(n?2)}\text{3}$] or $\text{[}\text{(n?2)}\text{3}\text{] + 1}$ vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes.     

An efficient algorithm to solve connectivity problem on trapezoid graphs

The connectivity problem is a fundamental problem in graph theory. The best known algorithm to solve the connectivity problem on general graphs withn vertices andm edges takesO(K(G)mn ^1.5) time, whereK(G) is the vertex connectivity ofG. In this paper, an efficient algorithm is designed to solve vertex connectivity problem, which takesO(n ²) time andO(n) space for a trapezoid 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)?     

Enumerating maximal independent sets with applications to graph colouring

We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph.