On the 3-restricted edge connectivity of permutation graphs

An edge cut W of a connected graph G is a k-restricted edge cut if G−W is disconnected, and every component of G−W has at least k vertices. The k-restricted edge connectivity is defined as the minimum cardinality over all k-restricted edge cuts. A permutation graph is obtained by taking two disjoint copies of a graph and adding a perfect matching between the two copies. The k-restricted edge connectivity of a permutation graph is upper bounded by the so-called minimum k-edge degree. In this paper some sufficient conditions guaranteeing optimal k-restricted edge connectivity and super k-restricted edge connectivity for permutation graphs are presented for k=2,3.     

The lower and upper forcing geodetic numbers of block–cactus graphs

A vertex set D in graph G is called a geodetic set if all vertices of G are lying on some shortest u–v path of G, where u, v ∈ D. The geodetic number of a graph G is the minimum cardinality among all geodetic sets. A subset S of a geodetic set D is called a forcing subset of D if D is the unique geodetic set containing S. The forcing geodetic number of D is the minimum cardinality of a forcing subset of D, and the lower and the upper forcing geodetic numbers of a graph G are the minimum and the maximum forcing geodetic numbers, respectively, among all minimum geodetic sets of G. In this paper, we find out the lower and the upper forcing geodetic numbers of block–cactus graphs.     

Maximum generic nullity of a graph

For a graph G of order n, the maximum nullity of G is defined to be the largest possible nullity over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. Maximum nullity and the related parameter minimum rank of the same set of matrices have been studied extensively. A new parameter, maximum generic nullity, is introduced. Maximum generic nullity provides insight into the structure of the null-space of a matrix realizing maximum nullity of a graph. It is shown that maximum generic nullity is bounded above by edge connectivity and below by vertex connectivity. Results on random graphs are used to show that as n goes to infinity almost all graphs have equal maximum generic nullity, vertex connectivity, edge connectivity, and minimum degree.     

Diameter-sufficient conditions for a graph to be super-restricted connected

A vertex-cut X is said to be a restricted cut of a graph G if it is a vertex-cut such that no vertex u in G has all its neighbors in X. Clearly, each connected component of G−X must have at least two vertices. The restricted connectivity κ^′(G) of a connected graph G is defined as the minimum cardinality of a restricted cut. Additionally, if the deletion of a minimum restricted cut isolates one edge, then the graph is said to be super-restricted connected. In this paper, several sufficient conditions yielding super-restricted-connected graphs are given in terms of the girth and the diameter. The corresponding problem for super-edge-restricted-connected graph is also studied.     

The least eigenvalue of graphs with given connectivity

Let G be a simple graph and A(G) be the adjacency matrix of G. The eigenvalues of G are those of A(G). In this paper, we characterize the graphs with the minimal least eigenvalue among all graphs of fixed order with given vertex connectivity or edge connectivity.     

Contributions to the theory of domination,independence and irredundance in graphs

A vertex x in a subset X of vertices of an undirected graph is redundant if its closed neighbourhood is contained in the union of closed neighbourhoods of vertices of X?{x}. In the context of a communications network, this means that any vertex which may receive communications from X may also be informed from X?{x}. The lower and upper irredundance numbers ir(G) and IR(G) are respectively the minimum and maximum cardinalities taken over all maximal sets of vertices having no redundancies. The domination number γ(G) and upper domination number Γ(G) are respectively the minimum and maximum cardinalities taken over all minimal dominating sets of G. The independent domination number i(G) and the independence number β(G) are respectively the minimum and maximum cardinalities taken over all maximal independent sets of vertices of G.A variety of inequalities involving these quantities are established and sufficient conditions for the equality of the three upper parameters are given. In particular a conjecture of Hoyler and Cockayne [9], namely $\text{i+β?2p + 2δ - 2}\text{2pδ}$, is proved.     

On trees with total domination number equal to edge-vertex domination number plus one

An edge e∈E(G) dominates a vertex v∈V(G) if e is incident with v or e is incident with a vertex adjacent to v. An edge-vertex dominating set of a graph G is a set D of edges of G such that every vertex of G is edge-vertex dominated by an edge of D. The edge-vertex domination number of a graph G is the minimum cardinality of an edge-vertex dominating set of G. A subset D?V(G) is a total dominating set of G if every vertex of G has a neighbor in D. The total domination number of G is the minimum cardinality of a total dominating set of G. We characterize all trees with total domination number equal to edge-vertex domination number plus one.     

On the bondage number of middle graphs

Let G = (V (G),E(G)) be a simple graph. A subset S of V (G) is a dominating set of G if, for any vertex v ∈ V (G) — S, there exists some vertex u ∈ S such that uv ∈ E(G). The domination number, denoted by γ(G), is the cardinality of a minimal dominating set of G. There are several types of domination parameters depending upon the nature of domination and the nature of dominating set. These parameters are bondage, reinforcement, strong-weak domination, strong-weak bondage numbers. In this paper, we first investigate the strong-weak domination number of middle graphs of a graph. Then several results for the bondage, strong-weak bondage number of middle graphs are obtained.     

Sufficient conditions for graphs to be λ′‐optimal,super‐edge‐connected,and maximally edge‐connected

The restricted‐edge‐connectivity of a graph G, denoted by λ′(G), is defined as the minimum cardinality over all edge‐cuts S of G, where G‐S contains no isolated vertices. The graph G is called λ′‐optimal, if λ′(G) = ξ(G), where ξ(G) is the minimum edge‐degree in G. A graph is super‐edge‐connected, if every minimum edge‐cut consists of edges adjacent to a vertex of minimum degree. In this paper, we present sufficient conditions for arbitrary, triangle‐free, and bipartite graphs to be λ′‐optimal, as well as conditions depending on the clique number. These conditions imply super‐edge‐connectivity, if δ (G) ≥ 3, and the equality of edge‐connectivity and minimum degree. Different examples will show that these conditions are best possible and independent of other results in this area. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 228–246, 2005     

The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ _k (G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U₁,U₂ ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U ₁ and the other in U ₂ by [U ₁, U ₂]. Define x_k(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ _k -optimal if λ _k (G) = ξ _k (G). A graph is said to be super-λ _k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ _k -optimal or super-λ _k . Moreover, we demonstrate that our results are best possible.     

Characterization of double domination subdivision number of trees

In a graph G, a vertex dominates itself and its neighbors. A subset S⊆V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The double domination numberdd(G) is the minimum cardinality of a double dominating set of G. The double domination subdivision numbersd_dd(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the double domination number. In this paper first we establish upper bounds on the double domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that sd_dd(G)?3. We also prove that 1?sd_dd(T)?2 for every tree T, and characterize the trees T for which sd_dd(T)=2.     

Graph-theoretic parameters concerning domination,independence, and irredundance

A vertex x in a subset X of vertices of an undericted graph is redundant if its closed neighbourhood is contained in the union of closed neighborhoods of vertices of X – {x}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X – {x}. The irredundance number ir (G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. The domination number γ(G) is the minimum cardinality taken over all dominating sets of G, and the independent domination number i(G) is the minimum cardinality taken over all maximal independent sets of vertices of G. The paper contians results that relate these parameters. For example, we prove that for any graph G, ir (G) > γ(G)/2 and for any grpah Gwith p vertices and no isolated vertices, i(G) ≤ p-γ(G) + 1 - ?(p - γ(G))/γ(G)?.     

A sharp upper bound on algebraic connectivity using domination number

Let G be a connected graph of order n. The algebraic connectivity of G is the second smallest eigenvalue of the Laplacian matrix of G. A dominating set in G is a vertex subset S such that each vertex of G that is not in S is adjacent to a vertex in S. The least cardinality of a dominating set is the domination number. In this paper, we prove a sharp upper bound on the algebraic connectivity of a connected graph in terms of the domination number and characterize the associated extremal graphs.     

The irredundance number and maximum degree of a graph

A vertex η in a subset X of vertices of an undirected graph is redundant if its closed neighborhood is contained in the union of closed neighborhoods of vertices of X-{η}. In the context of a communications network, this means that any vertex that may receive communications from X may also be informed from X-{η}. The irredundance number ir(G) is the minimum cardinality taken over all maximal sets of vertices having no redundancies. In this note we show that ir(G) ? n/(2Δ-1) for a graph G having n vertices and maximum degree Δ.     

Minimally 3-restricted edge connected graphs

For a connected graph G=(V,E), an edge set S⊂E is a 3-restricted edge cut if G−S is disconnected and every component of G−S has order at least three. The cardinality of a minimum 3-restricted edge cut of G is the 3-restricted edge connectivity of G, denoted by λ₃(G). A graph G is called minimally 3-restricted edge connected if λ₃(G−e)<λ₃(G) for each edge e∈E. A graph G is λ₃-optimal if λ₃(G)=ξ₃(G), where , ω(U) is the number of edges between U and V?U, and G[U] is the subgraph of G induced by vertex set U. We show in this paper that a minimally 3-restricted edge connected graph is always λ₃-optimal except the 3-cube.     

The eavesdropping number of a graph

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v, a minimum {u, v}-separating set is a smallest set of edges in G whose removal disconnects u and v. The edge connectivity of G, denoted λ(G), is defined to be the minimum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. We introduce and investigate the eavesdropping number, denoted ε(G), which is defined to be the maximum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families of graphs.     

On the restricted connectivity and superconnectivity in graphs with given girth

The restricted connectivity κ^′(G) of a connected graph G is defined as the minimum cardinality of a vertex-cut over all vertex-cuts X such that no vertex u has all its neighbors in X; the superconnectivity κ₁(G) is defined similarly, this time considering only vertices u in G-X, hence κ₁(G)?κ^′(G). The minimum edge-degree of G is ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, d(u) standing for the degree of a vertex u. In this paper, several sufficient conditions yielding κ₁(G)?ξ(G) are given, improving a previous related result by Fiol et al. [Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17-31] and guaranteeing κ₁(G)=κ^′(G)=ξ(G) under some additional constraints.     

Average distances and distance domination numbers

Let k be a positive integer and G be a simple connected graph with order n. The average distance μ(G) of G is defined to be the average value of distances over all pairs of vertices of G. A subset D of vertices in G is said to be a k-dominating set of G if every vertex of V(G)−D is within distance k from some vertex of D. The minimum cardinality among all k-dominating sets of G is called the k-domination number γ_k(G) of G. In this paper tight upper bounds are established for μ(G), as functions of n, k and γ_k(G), which generalizes the earlier results of Dankelmann [P. Dankelmann, Average distance and domination number, Discrete Appl. Math. 80 (1997) 21-35] for k=1.     

Edge-Coloring Bipartite Multigraphs in O(E logD) Time

Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E logD time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time. Received September 23, 1999     

Upper bounds on vertex distinguishing chromatic index of some Halin graphs

A vertex distinguishing edge coloring of a graph G is a proper edge coloring of G such that any pair of vertices has the distinct sets of colors. The minimum number of colors required for a vertex distinguishing edge coloring of a graph G is denoted by ???? _s (G). In this paper, we obtained upper bounds on the vertex distinguishing chromatic index of 3-regular Halin graphs and Halin graphs with ??(G) ?? 4, respectively.