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 local connectivity of graphs with given clique number

For a vertex v of a graph G, we denote by d(v) the degree of v. The local connectivity κ(u, v) of two vertices u and v in a graph G is the maximum number of internally disjoint u –v paths in G, and the connectivity of G is defined as κ(G)=min{κ(u, v)|u, v∈V(G)}. Clearly, κ(u, v)?min{d(u), d(v)} for all pairs u and v of vertices in G. Let δ(G) be the minimum degree of G. We call a graph G maximally connected when κ(G)=δ(G) and maximally local connected when for all pairs u and v of distinct vertices in G. In 2006, Hellwig and Volkmann (J Graph Theory 52 (2006), 7–14) proved that a connected graph G with given clique number ω(G)?p of order n(G) is maximally connected when As an extension of this result, we will show in this work that these conditions even guarantee that G is maximally local connected. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 192–197, 2010     

Geodesics and almost geodesic cycles in random regular graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d_G(u, v) is at least d_C(u, v)?e(n). Let ω(n) be any function tending to infinity with n. We consider a random d‐regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n) = log_d?1log_d?1n+ ω(n) and |C| = 2log_d?1n+ O(ω(n)). Along the way, we obtain results on near‐geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011     

The effects of distance and neighborhood union conditions on hamiltonian properties in graphs

We prove that a 2-connected graph G of order p is hamiltonian if for all distinct vertices u and v, dist(u,v) = 2 implies that |N(u) U N(v)| ? (2p - 1)/3. We also demonstrate hamiltonian-connected and traceability properties in graphs under similar conditions.     

Spanning trails

For a graph G with distinguished vertices u and v, we give a sufficient condition for the existence of a (u, v)-trail containing every vertex of G.     

Mapping Class Groups of Hyperbolic Surfaces and Automorphism Groups of Graphs

Let M be a hyperbolic surface and (M) its extended mapping class group. We show that (M) is isomorphic to the automorphism group of the following graph G(M). The set of vertices of G(M) is the set S(M) of nonseparating simple closed geodesics of M. Two vertices u and v of S(M) are related by an edge if u and v intersect exactly once in M. The graph G(M) can be thought of as a combinatorial model for M.     

A note on graphs with diameter-preserving spanning trees

The distance between a pair of vertices u, v in a graph G is the length of a shortest path joining u and v. The diameter diam(G) of G is the maximum distance between all pairs of vertices in G. A spanning tree T of G is diameter preserving if diam(T) = diam(G). In this note, we characterize graphs that have diameter-preserving spanning trees.     

Neighborhood unions and hamilton cycles

Let G be a graph on n vertices and N₂(G) denote the minimum size of N(u) ∪ N(v) taken over all pairs of independent vertices u, v of G. We show that if G is 3-connected and N₂(G) ? ½(n + 1), then G has a Hamilton cycle. We show further that if G is 2-connected and N₂(G) ? ½(n + 3), then either G has a Hamilton cycle or else G belongs to one of three families of exceptional graphs.     

Graph Connectivity After Path Removal

Let G be a graph and u, v be two distinct vertices of G. A u—v path P is called nonseparating if G—V(P) is connected. The purpose of this paper is to study the number of nonseparating u—v path for two arbitrary vertices u and v of a given graph. For a positive integer k, we will show that there is a minimum integer (k) so that if G is an (k)-connected graph and u and v are two arbitrary vertices in G, then there exist k vertex disjoint paths P ₁[u,v], P ₂[u,v], . . ., P _k [u,v], such that G—V (P _i [u,v]) is connected for every i (i = 1, 2, ..., k). In fact, we will prove that (k) 22k+2. It is known that (1) = 3.. A result of Tutte showed that (2) = 3. We show that (3) = 6. In addition, we prove that if G is a 5-connected graph, then for every pair of vertices u and v there exists a path P[u, v] such that G—V(P[u, v]) is 2-connected.* Supported by NSF grant No. DMS-0070059 Supported by ONR grant N00014-97-1-0499 Supported by NSF grant No. 9531824     

On induced subgraphs of a block

If G is a block, then a vertex u of G is called critical if G - u is not a block. In this article, relationships between the localization of critical vertices and the localization of vertices of relatively small degrees (especially, of degree two) are studied. A block is called semicritical if a) each edge is incident with at least one critical vertex and b) each vertex of degree two is critical. Let G be a semicritical block with at least six vertices. It is proved that A) there exist distinct vertices u₂, v₁, u₂, and v₂ of degree two in G such that u₁v₁ and u₂v₂ are edges of G, and u₁v₂, and u₂v₂ are edges of the complement of G, and B) the complement of G is a block with no critical vertex of degree two.     

On graphs satisfying a local ore-type condition

For an integer i, a graph is called an L_i-graph if, for each triple of vertices u, v, w with d(u, v) = 2 and w (element of) N(u) (intersection) N(v), d(u) + d(v) ≥ | N(u) (union) N(v) (union) N(w)| —i. Asratian and Khachatrian proved that connected L_o-graphs of order at least 3 are hamiltonian, thus improving Ore's Theorem. All K_1,3-free graphs are L₁-graphs, whence recognizing hamiltonian L₁-graphs is an NP-complete problem. The following results about L₁-graphs, unifying known results of Ore-type and known results on K_1,3-free graphs, are obtained. Set K = lcub;G|K_p,p+1 (contained within) G (contained within) K_p V K_p+1 for some ρ ≥ } (v denotes join). If G is a 2-connected L₁-graph, then G is 1-tough unless G (element of) K. Furthermore, if G is as connected L₁-graph of order at least 3 such that |N(u) (intersection) N(v)| ≥ 2 for every pair of vertices u, v with d(u, v) = 2, then G is hamiltonian unless G ϵ K, and every pair of vertices x, y with d(x, y) ≥ 3 is connected by a Hamilton path. This result implies that of Asratian and Khachatrian. Finally, if G is a connected L₁-graph of even order, then G has a perfect matching. © 1996 John Wiley & Sons, Inc.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and uv \not ? E(G)}{uv \not \in E(G)\}} , and NC₂(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.     

Long paths through four vertices in a 2‐connected graph

Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000     

Degree Distance of Unicyclic Graphs with Given Matching Number

Let G be a connected graph with vertex set V(G). The degree distance of G is defined as ${D'(G) = \sum_{\{u, v\}\subseteq V(G)} (d_G(u) + d_G (v))\, d(u,v)}$ , where d _G (u) is the degree of vertex u, d(u, v) denotes the distance between u and v, and the summation goes over all pairs of vertices in G. In this paper, we characterize n-vertex unicyclic graphs with given matching number and minimal degree distance.     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

On integral sum graphs with a saturated vertex

As introduced by F.Harary in 1994, a graph G is said to be an integral sum graph if its vertices can be given a labeling f with distinct integers so that for any two distinct vertices u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some vertex w in G.     

A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.     

On bounds for the cutting number of a graph

The cutting number of a vertex v of a finite graph G = (V,E) is a natural measure of the extent to which the removal of v disconnects the graph. Precisely, the cutting number c(v) of v is defined as the number of pairs of vertices {u,w} of G such that u,w ≠ v and every u-w path contains v. The cutting number c(G) of G is the maximum value of c(v) over all vertices in V. We provide exact bounds on the cutting number of G in terms of order and diameter of the graph.