Sharp upper and lower bounds for the Laplacian spectral radius and the spectral radius of graphs

In this paper, sharp upper bounds for the Laplacian spectral radius and the spectral radius of graphs are given, respectively. We show that some known bounds can be obtained from our bounds. For a bipartite graph G, we also present sharp lower bounds for the Laplacian spectral radius and the spectral radius, respectively.     

Complexity of the packing coloring problem for trees

Packing coloring is a partitioning of the vertex set of a graph with the property that vertices in the i-th class have pairwise distance greater than i. The main result of this paper is a solution of an open problem of Goddard et al. showing that the decision whether a tree allows a packing coloring with at most k classes is NP-complete.We further discuss specific cases when this problem allows an efficient algorithm. Namely, we show that it is decideable in polynomial time for graphs of bounded treewidth and diameter, and fixed parameter tractable for chordal graphs.We accompany these results by several observations on a closely related variant of the packing coloring problem, where the lower bounds on the distances between vertices inside color classes are determined by an infinite nondecreasing sequence of bounded integers.     

图的循环带宽和

Abstract. Let G be a simple graph. The cyclic bandwidth sum problem is to determine a labeling of graph G in a cycle such that the total length of edges is as small as possible. In this paper, some upper and lower bounds on cyclic bandwidth sum of graphs are studied.     

Thickness-Two Graphs Part Two: More New Nine-Critical Graphs,Independence Ratio,Cloned Planar Graphs,and Singly and Doubly Outerplanar Graphs

There are numerous means for measuring the closeness to planarity of a graph such as crossing number, splitting number, and a variety of thickness parameters. We focus on the classical concept of the thickness of a graph, and we add to earlier work in [4]. In particular, we offer new 9-critical thickness-two graphs on 17, 25, and 33 vertices, all of which provide counterexamples to a conjecture on independence ratio of Albertson; we investigate three classes of graphs, namely singly and doubly outerplanar graphs, and cloned planar graphs. We give a sharp upper bound for the largest chromatic number of the cloned planar graphs, and we give upper and lower bounds for the largest chromatic number of the former two classes.     

Efficient algorithms for finding critical subgraphs

This paper presents algorithms to find vertex-critical and edge-critical subgraphs in a given graph G, and demonstrates how these critical subgraphs can be used to determine the chromatic number of G. Computational experiments are reported on random and DIMACS benchmark graphs to compare the proposed algorithms, as well as to find lower bounds on the chromatic number of these graphs. We improve the best known lower bound for some of these graphs, and we are even able to determine the chromatic number of some graphs for which only bounds were known.     

A projection technique for partitioning the nodes of a graph

LetG=(N,E) be an undirected graph. We present several new techniques for partitioning the node setN intok disjoint subsets of specified sizes. These techniques involve eigenvalue bounds and tools from continuous optimization. Comparisons with examples taken from the literature show these techniques to be very successful.     

Energy of generalized line graphs

The energy of a graph is equal to the sum of the absolute values of its eigenvalues. Line graphs play an important role in the study of graph theory. Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. In this paper, we establish relations between the energy of the generalized line graph of a graph G and the Laplacian and signless Laplacian energies of G. We give upper and lower bounds for the energy of generalized line graphs. Finally, we present upper and lower bounds for some special graphs.     

Expected hitting and cover times of random walks on some special graphs

We give general bounds (and in some cases exact values) for the expected hitting and cover times of the simple random walk on some special undirected connected graphs using symmetry and properties of electrical networks. In particular we give easy proofs for an N–1H_N-1 lower bound and an N² upper bound for the cover time of symmetric graphs and for the fact that the cover time of the unit cube is Φ(NlogN). We giver a counterexample to a conjecture of Freidland about a general bound for hitting times. Using the electric approach, we provide some genral upper and lower bounds for the expected cover times in terms of the diameter of the graph. These bounds are tight in many instances, particularly when the graph is a tree. © 1994 John Wiley & Sons, Inc.     

Size-constrained graph partitioning polytopes

We consider the problem of clustering a set of items into subsets whose sizes are bounded from above and below. We formulate the problem as a graph partitioning problem and propose an integer programming model for solving it. This formulation generalizes several well-known graph partitioning problems from the literature like the clique partitioning problem, the equi-partition problem and the k-way equi-partition problem. In this paper, we analyze the structure of the corresponding polytope and prove several results concerning the facial structure. Our analysis yields important results for the closely related equi-partition and k-way equi-partition polytopes as well.     

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.     

Maximal and minimal entry in the principal eigenvector for the distance matrix of a graph

Let G=(V,E) be a simple, connected and undirected graph with vertex set V(G) and edge set E(G). Also let D(G) be the distance matrix of a graph G (Jane?i? et al., 2007) [13]. Here we obtain Nordhaus–Gaddum-type result for the spectral radius of distance matrix of a graph.A sharp upper bound on the maximal entry in the principal eigenvector of an adjacency matrix and signless Laplacian matrix of a simple, connected and undirected graph are investigated in Das (2009) [4] and Papendieck and Recht (2000) [15]. Generally, an upper bound on the maximal entry in the principal eigenvector of a symmetric nonnegative matrix with zero diagonal entries and without zero diagonal entries are investigated in Zhao and Hong (2002) [21] and Das (2009) [4], respectively. In this paper, we obtain an upper bound on minimal entry in the principal eigenvector for the distance matrix of a graph and characterize extremal graphs. Moreover, we present the lower and upper bounds on maximal entry in the principal eigenvector for the distance matrix of a graph and characterize extremal graphs.     

Upper Bounds for the Laplacian Graph Eigenvalues

We first apply non-negative matrix theory to the matrix K = D A, where D and A are the degree-diagonal and adjacency matrices of a graph G, respectively, to establish a relation on the largest Laplacian eigenvalue λ1 (G) of G and the spectral radius p(K) of K. And then by using this relation we present two upper bounds for λ1(G) and determine the extremal graphs which achieve the upper bounds.     

Cyclicity of graphs

The cyclicity of a graph is the largest integer n for which the graph is contractible to the cycle on n vertices. By analyzing the cycle space of a graph, we establish upper and lower bounds on cyclicity. These bounds facilitate the computation of cyclicity for several classes of graphs, including chordal graphs, complete n-partite graphs, n-cubes, products of trees and cycles, and planar graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 160–170, 1999     

Three new upper bounds on the chromatic number

This paper introduces three new upper bounds on the chromatic number, without making any assumptions on the graph structure. The first one, ξ, is based on the number of edges and nodes, and is to be applied to any connected component of the graph, whereas ζ and η are based on the degree of the nodes in the graph. The computation complexity of the three-bound computation is assessed. Theoretical and computational comparisons are also made with five well-known bounds from the literature, which demonstrate the superiority of the new upper bounds.     

Linear and quadratic programming approaches for the general graph partitioning problem

The graph partitioning problem is to partition the vertex set of a graph into a number of nonempty subsets so that the total weight of edges connecting distinct subsets is minimized. Previous research requires the input of cardinalities of subsets or the number of subsets for equipartition. In this paper, the problem is formulated as a zero-one quadratic programming problem without the input of cardinalities. We also present three equivalent zero-one linear integer programming reformulations. Because of its importance in data biclustering, the bipartite graph partitioning is also studied. Several new methods to determine the number of subsets and the cardinalities are presented for practical applications. In addition, hierarchy partitioning and partitioning of bipartite graphs without reordering one vertex set, are studied.     

Inequalities for the Grundy chromatic number of graphs

The Grundy (or First-Fit) chromatic number of a graph G is the maximum number of colors used by the First-Fit coloring of the graph G. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number.     

Partitions of graphs into cographs

Cographs form the minimal family of graphs containing K₁ that is closed with respect to complementation and disjoint union. We discuss vertex partitions of graphs into the smallest number of cographs. We introduce a new parameter, calling the minimum order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show that both bounds are sharp for graphs with arbitrarily high girth. This provides an alternative proof to a result by Broere and Mynhardt; namely, there exist triangle-free graphs with arbitrarily large c-chromatic numbers. We show that any planar graph with girth at least 11 has a c-chromatic number at most two. We close with several remarks on computational complexity. In particular, we show that computing the c-chromatic number is NP-complete for planar graphs.     

Achievable sets, brambles, and sparse treewidth obstructions

One consequence of the graph minor theorem is that for every k there exists a finite obstruction set Obs(TW?k). However, relatively little is known about these sets, and very few general obstructions are known. The ones that are known are the cliques, and graphs which are formed by removing a few edges from a clique. This paper gives several general constructions of minimal forbidden minors which are sparse in the sense that the ratio of the treewidth to the number of vertices n does not approach 1 as n approaches infinity. We accomplish this by a novel combination of using brambles to provide lower bounds and achievable sets to demonstrate upper bounds. Additionally, we determine the exact treewidth of other basic graph constructions which are not minimal forbidden minors.     

The k‐piece packing problem

A k‐piece of a graph G is a connected subgraph of G all of whose nodes have degree at most k and at least one node has degree equal to k. We consider the problem of covering the maximum number of nodes of a graph by node disjoint k‐pieces. When k = 1 this is the maximum matching problem, and when k = 2 this is the problem, recently studied by Kaneko [ 19 [, of covering the maximum number of nodes by disjoint paths of length greater than 1. We present a polynomial time algorithm for the problem as well as a Tutte‐type existence theorem and a Berge‐type min‐max formula. We also solve the problem in the more general situation where the “pieces” are defined in terms of lower and upper bounds on the degrees. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Intersections of graphs

The study of graph homomorphisms has a long and distinguished history, with applications in many areas of graph theory. There has been recent interest in counting homomorphisms, and in particular on the question of finding upper bounds for the number of homomorphisms from a graph G into a fixed image graph H. We introduce our techniques by proving that the lex graph has the largest number of homomorphisms into K₂ with one looped vertex (or equivalently, the largest number of independent sets) among graphs with fixed number of vertices and edges. Our main result is the solution to the extremal problem for the number of homomorphisms into P, the completely looped path of length 2 (known as the Widom–Rowlinson model in statistical physics). We show that there are extremal graphs that are threshold, give explicitly a list of five threshold graphs from which any threshold extremal graph must come, and show that each of these “potentially extremal” threshold graphs is in fact extremal for some number of edges. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 261–284, 2011