Diameter increase caused by edge deletion

We consider the following problem: Given positive integers k and D, what is the maximum diameter of the graph obtained by deleting k edges from a graph G with diameter D, assuming that the resulting graph is still connected? For undirected graphs G we prove an upper bound of (k + 1)D and a lower bound of (k + 1)D ? k for even D and of (k + 1)D ? 2k + 2 for odd D ? 3. For the special cases of k = 2 and k = 3, we derive the exact bounds of 3D ? 1 and 4D ? 2, respectively. For D = 2 we prove exact bounds of k + 2 and k + 3, for k ? 4 and k = 6, and k = 5 and k ? 7, respectively. For the special case of D = 1 we derive an exact bound on the resulting maximum diameter of order θ(√k). For directed graphs G, the bounds depend strongly on D: for D = 1 and D = 2 we derive exact bounds of θ(√k) and of 2k + 2, respectively, while for D ? 3 the resulting diameter is in general unbounded in terms of k and D. Finally, we prove several related problems NP-complete.     

On Linear Programming Bounds for Spherical Codes and Designs

We investigate universal bounds on spherical codes and spherical designs that could be obtained using Delsartes linear programming methods. We give a lower estimate for the LP upper bound on codes, and an upper estimate for the LP lower bound on designs. Specifically, when the distance of the code is fixed and the dimension goes to infinity, the LP upper bound on codes is at least as large as the average of the best known upper and lower bounds. When the dimension n of the design is fixed, and the strength k goes to infinity, the LP bound on designs turns out, in conjunction with known lower bounds, to be proportional to k^n-1.     

Minor‐order obstructions for the graphs of vertex cover 6

We provide for the first time, a complete list of forbidden minors (obstructions) for the family of graphs with vertex cover 6. This study shows how to limit both the search space of graphs and improve the efficiency of an obstruction checking algorithm when restricted to k–VERTEX COVER graph families. In particular, our upper bounds 2k + 1 (2k + 2) on the maximum number of vertices for connected (disconnected) obstructions are shown to be sharp for all k > 0. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 163–178, 2002     

Justifying the small‐world phenomenon via random recursive trees

We present a new technique for proving logarithmic upper bounds for diameters of evolving random graph models, which is based on defining a coupling between random graphs and variants of random recursive trees. The advantage of the technique is three‐fold: it is quite simple and provides short proofs, it is applicable to a broad variety of models including those incorporating preferential attachment, and it provides bounds with small constants. We illustrate this by proving, for the first time, logarithmic upper bounds for the diameters of the following well known models: the forest fire model, the copying model, the PageRank‐based selection model, the Aiello‐Chung‐Lu models, the generalized linear preference model, directed scale‐free graphs, the Cooper‐Frieze model, and random unordered increasing k‐trees. Our results shed light on why the small‐world phenomenon is observed in so many real‐world graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 201–224, 2017     

Looseness of Plane Graphs

A face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained.     

On the embedding of graphs into graphs with few eigenvalues

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic graphs of type k for every k ≥ 3. Furthermore, in the case k ≥ 5 such a family of extensions can be found at every sufficiently large order. Some bounds for the extension will also be given. © 1996 John Wiley & Sons, Inc.     

The kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs

In this article, we study the kth upper and lower bases of primitive nonpowerful minimally strong signed digraphs. A bound on the kth upper bases for primitive nonpowerful minimally strong signed digraphs is obtained, and the equality case of the bound is characterized. For the kth lower bases, we obtain some bounds. For some cases, the bounds are best possible and the extremal signed digraphs are characterized. We also show that there exist ‘gaps’ in both the kth upper base set and the kth lower base set of primitive nonpowerful minimally strong signed digraphs.     

An upper bound for the total chromatic number of dense graphs

In this paper we consider those graphs that have maximum degree at least 1/k times their order, where k is a (small) positive integer. A result of Hajnal and Szemerédi concerning equitable vertex-colorings and an adaptation of the standard proof of Vizing's Theorem are used to show that if the maximum degree of a graph G satisfies Δ(G) ≥ |V(G)/k, then X″(G) ≤ Δ(G) + 2k + 1. This upper bound is an improvement on the currently available upper bounds for dense graphs having large order.     

New Linear Codes with Covering Radius 2 and Odd Basis

On the way of generalizing recent results by Cock and the second author, it is shown that when the basis q is odd, BCH codes can be lengthened to obtain new codes with covering radius R=2. These constructions (together with a lengthening construction by the first author) give new infinite families of linear covering codes with codimension r=2k+1 (the case q=3, r=4k+1 was considered earlier). New code families with r=4k are also obtained. An updated table of upper bounds on the length function for linear codes with 24, R=2, and q=3,5 is given.     

Randomized greedy algorithms for finding small k‐dominating sets of regular graphs

A k‐dominating set of a graph G is a subset ?? of the vertices of G such that every vertex of G is either in ?? or at distance at most k from a vertex in ??. It is of interest to find k‐dominating sets of small cardinality. In this paper we consider simple randomized greedy algorithms for finding small k‐dominating sets of regular graphs. We analyze the average‐case performance of the most efficient of these simple heuristics showing that it performs surprisingly well on average. The analysis is performed on random regular graphs using differential equations. This, in turn, proves upper bounds on the size of a minimum k‐dominating set of random regular graphs. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 22, 2005     

Edge Maximal Non-Bipartite Graphs Without Odd Cycles of Prescribed Lengths

 Let ?(n;3,5,…,2k+1) denote the class of non-bipartite graphs on n vertices having no odd cycle of length ≤2k+1. We prove that for every G∈?(n;3,5,…,2k+1) and characterize the extremal graphs. We also study the subclass ℋ(n;3,5,…,2k+1) consisting of the hamiltonian members of ?(n;3,5,…, 2k+1). For this subclass the above upper bound holds for odd n. For even n we establish the following sharp upper bound:

A computational study of graph partitioning

LetG = (N, E) be an edge-weighted undirected graph. The graph partitioning problem is the problem of partitioning the node setN intok disjoint subsets of specified sizes so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. We present a numerical study on the use of eigenvalue-based techniques to find upper and lower bounds for this problem. Results for bisecting graphs with up to several thousand nodes are given, and for small graphs some trisection results are presented. We show that the techniques are very robust and consistently produce upper and lower bounds having a relative gap of typically a few percentage points.Corresponding author.     

On the number of maximal bipartite subgraphs of a graph

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ⁿ; such subgraphs show an upper bound of O(12^n/4) = O(1.8613ⁿ) and give an algorithm that finds all maximal induced bipartite subgraphs in time within a polynomial factor of this bound. This algorithm is used in the construction of algorithms for checking k‐colorability of a graph. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 127–132, 2005     

On replete graphs

A graph G is k-clique replete if G has clique number k and every elementary homomorphism of G has clique number greater than k. Results on the order of k-clique replete graphs are presented, and bounds for the minimum degree and the maximum degree of such graphs are discussed.     

Lower bounds of the Laplacian graph eigenvalues

In this paper we prove that all positive eigenvalues of the Laplacian of an arbitrary simple graph have some positive lower bounds. For a fixed integer k 1 we call a graph without isolated vertices k-minimal if its kth greatest Laplacian eigenvalue reaches this lower bound. We describe all 1-minimal and 2-minimal graphs and we prove that for every k 3 the path P_k+1 on k + 1 vertices is the unique k-minimal graph.     

On crossing numbers of geometric proximity graphs

Let P be a set of n points in the plane. A geometric proximity graph on P is a graph where two points are connected by a straight-line segment if they satisfy some prescribed proximity rule. We consider four classes of higher order proximity graphs, namely, the k-nearest neighbor graph, the k-relative neighborhood graph, the k-Gabriel graph and the k-Delaunay graph. For k=0 (k=1 in the case of the k-nearest neighbor graph) these graphs are plane, but for higher values of k in general they contain crossings. In this paper, we provide lower and upper bounds on their minimum and maximum number of crossings. We give general bounds and we also study particular cases that are especially interesting from the viewpoint of applications. These cases include the 1-Delaunay graph and the k-nearest neighbor graph for small values of k.     

Improved bounds for the Laplacian energy of Bethe trees

For k, d?2, a Bethe tree is a rooted tree with k levels which the root vertex has degree d, the vertices from level 2 to k-1 have degree d+1 and the vertices at the level k are pendent vertices. So et al, using a theorem by Ky Fan have obtained both upper and lower bounds for the Laplacian energy of bipartite graphs. We shall employ the above mentioned theorem to obtain new and improved bounds for the Laplacian energy in the case of Bethe trees.     

Upper Bounds on the Dual Distance of BCH(255, k)

To obtain upper bounds on the distance of a binary linear code, many probabilistic algorithms have been proposed. The author presents a general variation to these algorithms, specific for cyclic codes, which is shown to be an improvement. As an example, the author optimizes Brouwer's algorithm to find the best upper bounds on the dual distance of BCH[255,k,d].     

Edge integrity of nearest neighbor graphs and separator theorems

We give upper bounds for the edge integrity and the vertex integrity of $k$-type nearest neighbor graphs in ${\mathbb{R}}^d$. For $n$ the order of a graph, examples are constructed to show that the bounds are best possible in the parameters $n$ and $k$. The results follow from decompositions that are shown for certain graphs that possess small edge or vertex separators. A vertex separator theorem for nearest neighbor graphs is known, and an edge separator theorem is shown. We also apply the decompositions to obtain upper bounds for the edge integrity of planar graphs, graphs of fixed genus, and trees.     

k-Independence and the k-residue of a graph

Favaron, Mahéo, and Saclé proved that the residue of a simple graph G is a lower bound on its independence number α (G). For k ∈ ℕ, a vertex set X in a graph is called k-independent, if the subgraph induced by X has maximum degree less than k. We prove that a generalization of the residue, the k-residue of a graph, yields a lower bound on the k-independence number. The new bound strengthens a bound of Caro and Tuza and improves all known bounds for some graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 241–249, 1999