Multiple bifurcation from “simple” eigenvalues

Consider an operator equation G(u,λ) = 0 where λ is a real parameter. Suppose 0 is a “simple” eigenvalue of the Fréchet derivative G_u at (u₀, λ₀). We give a hierarchy of conditions which completely determines the solution structure of the operator equation. It will be shown that multiple bifurcation as well as simple bifurcation can occur. This extends the standard bifurcation theory from a simple eigenvalue in which only one branch bifurcates. We also discuss limit point bifurcations. Applications to semilinear elliptic equations and the homotopy method for the matrix eigenvalue problem are also given.     

Bounds on eigenvalues and chromatic numbers

We give new bounds on eigenvalue of graphs which imply some known bounds. In particular, if T(G) is the maximum sum of degrees of vertices adjacent to a vertex in a graph G, the largest eigenvalue ρ(G) of G satisfies with equality if and only if either G is regular or G is bipartite and such that all vertices in the same part have the same degree. Consequently, we prove that the chromatic number of G is at most with equality if and only if G is an odd cycle or a complete graph, which implies Brook's theorem. A generalization of this result is also given.     

No-hole L(2,1)-colorings

An L(2,1)-coloring of a graph G is a coloring of G's vertices with integers in {0,1,…,k} so that adjacent vertices’ colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span λ(G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is λ(G), and the hole index ρ(G) of G is the minimum number of colors in {0,1,…,λ(G)} not used in a span coloring. We say that G is full-colorable if ρ(G)=0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span μ(G) of G as ∞ if G has no no-hole coloring; otherwise μ(G) is the minimum k for which G has a no-hole coloring using colors in {0,1,…,k}.

Let n denote the number of vertices of G, and let Δ be the maximum degree of vertices of G. Prior work shows that all non-star trees with Δ3 are full-colorable, all graphs G with n=λ(G)+1 are full-colorable, μ(G)λ(G)+ρ(G) if G is not full-colorable and nλ(G)+2, and G has a no-hole coloring if and only if nλ(G)+1. We prove two extremal results for colorings. First, for every m1 there is a G with ρ(G)=m and μ(G)=λ(G)+m. Second, for every m2 there is a connected G with λ(G)=2m, n=λ(G)+2 and ρ(G)=m.     

Large eigenvalues of the laplacian

Let G be a simple graph on n vertices and let L=L(G) be the Laplacian matrix of G corresponding to some ordering of the vertices. It is known that λ≤n for any eigenvalue λ of L. In this note we characterize when n is an eigenvalue of L with multiplicity m.     

On the extreme eigenvalues of hermitian (block) toeplitz matrices

We are concerned with the behavior of the minimum (maximum) eigenvalue λ₀⁽ⁿ⁾ (λ_n⁽ⁿ⁾) of an (n + 1) × (n + 1) Hermitian Toeplitz matrix T_n(ƒ) where ƒ is an integrable real-valued function. Kac, Murdoch, and Szegö, Widom, Parter, and R. H. Chan obtained that λ₀⁽ⁿ⁾ — min ƒ = O(1/n^2k) in the case where ƒ C^2k, at least locally, and ƒ — inf ƒ has a zero of order 2k. We obtain the same result under the second hypothesis alone. Moreover we develop a new tool in order to estimate the extreme eigenvalues of the mentioned matrices, proving that the rate of convergence of λ₀⁽ⁿ⁾ to inf ƒ depends only on the order ρ (not necessarily even or integer or finite) of the zero of ƒ — inf ƒ. With the help of this tool, we derive an absolute lower bound for the minimal eigenvalues of Toeplitz matrices generated by nonnegative L¹ functions and also an upper bound for the associated Euclidean condition numbers. Finally, these results are extended to the case of Hermitian block Toeplitz matrices with Toeplitz blocks generated by a bivariate integrable function ƒ.     

The Hoffman number of a graph

For a connected graph G with n vertices, let {λ₁,λ₂,…,λ_r} be the set of distinct positive eigenvalues of the Laplacian matrix of G. The Hoffman number μ(G) of G is defined by μ(G)=λ₁λ₂…λ_r/n. In this paper, we study some properties and applications of the Hoffman number.     

Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)

The least eigenvalue of a connected graph is the least eigenvalue of its adjacency matrix. We characterize the connected graphs of order n and size n + k (5≤k≤8 and n>k + 5) with the minimal least eigenvalue.     

Number of minimum vertex cuts in transitive graphs

Let G be a k-regular vertex transitive graph with connectivity κ(G)=k and let m_k(G) be the number of vertex cuts with k vertices. Define m(n,k)=min{m_k(G): GT_n,k}, where T_n,k denotes the set of all k-regular vertex transitive graphs on n vertices with κ(G)=k. In this paper, we determine the exact values of m(n,k).     

Eigenvalue interlacing and weight parameters of graphs

Eigenvalue interlacing is a versatile technique for deriving results in algebraic combinatorics. In particular, it has been successfully used for proving a number of results about the relation between the (adjacency matrix or Laplacian) spectrum of a graph and some of its properties. For instance, some characterizations of regular partitions, and bounds for some parameters, such as the independence and chromatic numbers, the diameter, the bandwidth, etc., have been obtained. For each parameter of a graph involving the cardinality of some vertex sets, we can define its corresponding weight parameter by giving some “weights” (that is, the entries of the positive eigenvector) to the vertices and replacing cardinalities by square norms. The key point is that such weights “regularize” the graph, and hence allow us to define a kind of regular partition, called “pseudo-regular,” intended for general graphs. Here we show how to use interlacing for proving results about some weight parameters and pseudo-regular partitions of a graph. For instance, generalizing a well-known result of Lovász, it is shown that the weight Shannon capacity Θ^* of a connected graph Γ, with n vertices and (adjacency matrix) eigenvalues λ₁ > λ₂ … λ_n, satisfies

where Θ is the (standard) Shannon capacity and v is the positive eigenvector normalized to have smallest entry 1. In the special case of regular graphs, the results obtained have some interesting corollaries, such as an upper bound for some of the multiplicities of the eigenvalues of a distance-regular graph. Finally, some results involving the Laplacian spectrum are derived.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

Reconstruction of infinite locally finite connected graphs

Let G be an infinite locally finite connected graph. We study the reconstructibility of G in relation to the structure of its end set . We prove that an infinite locally finite connected graph G is reconstructible if there exists a finite family (Ω_i)_0i (n2) of pairwise finitely separable subsets of such that, for all x,y,x′,y′V(G) and every isomorphism f of G−{x,y} onto G−{x′,y′} there is a permutation π of {0,…,n−1} such that for 0i<n. From this theorem we deduce, as particular consequences, that G is reconstructible if it satisfies one of the following properties: (i) G contains no end-respecting subdivision of the dyadic tree and has at least two ends of maximal order; (ii) the set of thick ends or the one of thin ends of G is finite and of cardinality greater than one. We also prove that if almost all vertices of G are cutvertices, then G is reconstructible if it contains a free end or if it has at least a vertex which is not a cutvertex.     

Bandwidth of the composition of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)−f(y)| : xyE(G)} taken over all proper numberings f of G. The composition of two graphs G and H, written as G[H], is the graph with vertex set V(G)×V(H) and with (u₁,v₁) is adjacent to (u₂,v₂) if either u₁ is adjacent to u₂ in G or u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the composition of two graphs. Let G be a connected graph. We denote the diameter of G by D(G). For two distinct vertices x,yV(G), we define w_G(x,y) as the maximum number of internally vertex-disjoint (x,y)-paths whose lengths are the distance between x and y. We define w(G) as the minimum of w_G(x,y) over all pairs of vertices x,y of G with the distance between x and y is equal to D(G). Let G be a non-complete connected graph and let H be any graph. Among other results, we prove that if |V(G)|=B(G)D(G)−w(G)+2, then B(G[H])=(B(G)+1)|V(H)|−1. Moreover, we show that this result determines the bandwidth of the composition of some classes of graphs composed with any graph.     

Random packing by ρ-connected ρ-regular graphs

A graph G is packable by the graph F if its edges can be partitioned into copies of F. If deleting the edges of any F-packable subgraph from G leaves an F-packable graph, then G is randomly F-packable. If G is F-packable but not randomly F-packable then G is F-forbidden. The minimal F-forbidden graphs provide a characterization of randomly F-packable graphs. We show that for each ρ-connected ρ-regular graph F with ρ > 1, there is a set (F) of minimal F-forbidden graphs of a simple form, such that any other minimal F-forbidden graph can be obtained from a graph in (F) by a process of identifying vertices and removing copies of F. When F is a connected strongly edge-transitive graph having more than one edge (such as a cycle or hypercube), there is only one graph in (F).     

The chromatic difference sequence of the Cartesian product of graphs

The chromatic difference sequence cds(G) of a graph G with chromatic number n is defined by cds(G) = (a(1), a(2),…, a(n)) if the sum of a(1), a(2),…, a(t) is the maximum number of vertices in an induced t-colorable subgraph of G for t = 1, 2,…, n. The Cartesian product of two graphs G and H, denoted by G□H, has the vertex set V(G□H = V(G) x V(H) and its edge set is given by (x₁, y₁)(x₂, y₂) ε E(G□H) if either x₁ = x₂ and y₁ y₂ ε E(H) or y₁ = y₂ and x₁x₂ ε E(G).

We obtained four main results: the cds of the product of bipartite graphs, the cds of the product of graphs with cds being nondrop flat and first-drop flat, the non-increasing theorem for powers of graphs and cds of powers of circulant graphs.     

Lower bounds on the third smallest laplacian eigenvalue of a graph

We introduce a new graph-theoretic invariant ω(G) for a simple graph G, and relate it to the third smallest Laplace eigenvalue of G.     

On total covers of graphs

A total cover of a graph G is a subset of V(G)E(G) which covers all elements of V(G)E(G). The total covering number ₂(G) of a graph G is the minimum cardinality of a total cover in G. In [1], it is proven that ₂(G)[n/2] for a connected graph G of order n. Here we consider the extremal case and give some properties of connected graphs which have a total covering number [n/2]. We prove that such a graph with even order has a 1-factor and such a graph with odd order is factor-critical.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

Some results on characterizing the edges of connected graphs with a given domination number

A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m₁ (G, D) denote the number of edges that have neither endpoint in D, and let m₂ (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m₁ (G, D), m₂ (G, D)) can attain for connected graphs having a given domination number.     

ContributionsAcyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.