Independent edges in bipartite graphs obtained from orientations of graphs

Given a digraph D on vertices v₁, v₂, ?, v_n, we can associate a bipartite graph B(D) on vertices s₁, s₂, ?, s_n, t₁, t₂, ?, t_n, where s_it_j is an edge of B(D) if (v_i, v_j) is an arc in D. Let O_G denote the set of all orientations on the (undirected) graph G. In this paper we will discuss properties of the set S(G) := {β₁ (B(D))) | D ? O_G}, where β₁ is the edge independence number. In the first section we present some background and related concepts. We show that sets of the form S(G) are convex and that max S(G) ≦ 2 min S(G). Furthermore, this completely characterizes such sets. In the second section we discuss some bounds on elements of S(G) in terms of more familiar graphical parameters. The third section deals with extremal problems. We discuss bounds on elements of S(G) if the order and size of G are known, particularly when G is bipartite. In this section we exhibit a relation between max S(G) and the concept of graphical closure. In the fourth and final section we discuss the computational complexity of computing min S(G) and max S(G). We show that the first problem is NP-complete and that the latter is polynomial.     

On Cycles in 3-Connected Graphs

 Let G be a 3-connected graph of order n and S a subset of vertices. Denote by δ(S) the minimum degree (in G) of vertices of S. Then we prove that the circumference of G is at least min{|S|, 2δ(S)} if the degree sum of any four independent vertices of S is at least n+6. A cycle C is called S-maximum if there is no cycle C ^′ with |C ^′∩S|>|C∩S|. We also show that if ∑⁴ _i=1 d(a _i)≥n+3+|⋂⁴ _i=1 N(a _i)| for any four independent vertices a ₁, a ₂, a ₃, a ₄ in S, then G has an S-weak-dominating S-maximum cycle C, i.e. an S-maximum cycle such that every component in G−C contains at most one vertex in S. Received: March 9, 1998 Revised: January 7, 1999     

Covering the vertices of a graph by cycles of prescribed length

The main theorem of that paper is the following: let G be a graph of order n, of size at least (n² - 3n + 6)/2. For any integers k, n₁, n₂,…,n_k such that n = n₁ + n₂ +. + n_k and n_i ? 3, there exists a covering of the vertices of G by disjoint cycles (C_i) =l…k with |C_i| = ni, except when n = 6, n₁ = 3, n₂ = 3, and G is isomorphic to G₁, the complement of G₁ consisting of a C₃ and a stable set of three vertices, or when n = 9, n₁ = n₂ = n₃ = 3, and G is isomorphic to G₂, the complement of G₂ consisting of a complete graph on four vertices and a stable set of five vertices. We prove an analogous theorem for bipartite graphs: let G be a bipartite balanced graph of order 2n, of size at least n² - n + 2. For any integers s, n₁, n₂,…,n_s with n_i ? 2 and n = n₁ + n₂ + ? + n_s, there exists a covering of the vertices of G by s disjoint cycles C_i, with |C_i| = 2n_i.     

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.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

Vertex-switching,isomorphism, and pseudosimilarity

A vertex-switching G_s of a graph G is obtained by deleting from G all edges of G with exactly one end in the set of vertices S, and then adding to G all edges of the complement of G with exactly one end in S. We characterize the situations in which G_s is isomorphic to G, a result with application to the vertex-switching reconstruction problem. We use these results to construct pairs of vertex-switching pseudosimilar vertices, nonsimilar vertices u and v in a graph G with G_{u} isomorphic to G_{v}. We show that every such pair can be constructed by our methods.     

On hamiltonian-connected graphs

One of the most fundamental results concerning paths in graphs is due to Ore: In a graph G, if deg x + deg y ≧ |V(G)| + 1 for all pairs of nonadjacent vertices x, y ? V(G), then G is hamiltonian-connected. We generalize this result using set degrees. That is, for S ? V(G), let deg S = |_x?S N(x)|, where N(x) = {v|xv ? E(G)} is the neighborhood of x. In particular we show: In a 3-connected graph G, if deg S₁ + deg S₂ ≧ |V(G)| + 1 for each pair of distinct 2-sets of vertices S₁, S₂ ? V(G), then G is hamiltonian-connected. Several corollaries and related results are also discussed.     

An improvement of fraisse's sufficient condition for hamiltonian graphs

Let G be a k-connected graph of order n. For an independent set c, let d(S) be the number of vertices adjacent to at least one vertex of S and > let i(S) be the number of vertices adjacent to at least |S| vertices of S. We prove that if there exists some s, 1 ≤ s ≤ k, such that Σ_xiEX d(X\{X_i}) > s(n?1) – k[s/2] – i(X)[(s?1)/2] holds for every independetn set X ={x₀, x₁ ?x_s} of s + 1 vertices, then G is hamiltonian. Several known results, including Fraisse's sufficient condition for hamiltonian graphs, are dervied as corollaries.     

Proportional graphs

Let S be a finite set of graphs and t a real number, 0 < t < 1. A (deterministic) graph G is (t, 5)-proportional if for every H ∈ S, the number of induced subgraphs of G isomorphic to H equals the expected number of induced copies of H in the random graph G_{n, t} where n = |V(G)|. Let S_k = {all graphs on k vertices}, in particular S₃ = {K₃, P₂, K₂K_t, D₃}. The notion of proportional graphs stems from the study of random graphs (Barbour, Karoński, and Ruciński, J Combinat. Th. Ser. B, 47 , 125-145, 1989; Janson and Nowicki, Prob. Th. Rel. Fields, to appear, Janson, Random Struct. Alg., 1 , 15-37, 1990) where it is shown that (t, S₃)-proportional graphs play a very special role; we thus call them simply t-proportional. However, only a few ½-proportional graphs on 8 vertices were known and it was an open problem whether there are any f-proportional graphs with t ≠ ½ at all. In this paper, we show that there are infinitely many ½-proportional graphs and that there are t-proportional graphs with t≠. Both results are proved constructively. [We are not able to provide the latter construction for all f∈ Q∩(0,1), but the set of ts for which our construction works is dense in (0,1).] To support a conviction that the existence of (t, S₃)-proportional graphs was not quite obvious, we show that there are no (t, S₄)-proportional graphs.     

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

Sets that are connected in two random graphs

–We consider two random graphs G₁, G₂, both on the same vertex set. We ask whether there is a non‐trivial set of vertices S, so that S induces a connected subgraph both in G₁ and in G₂. We determine the threshold for the appearance of such a subset, as well as the size of the largest such subset. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 498–512, 2014     

Insertible vertices,neighborhood intersections,and hamiltonicity

Let G be a simple undirected graph of order n. For an independent set S ? V(G) of k vertices, we define the k neighborhood intersections S_i = {v ? V(G)&#92;S|N(v) ∩ S| = i}, 1 ≦ i ≦ k, with s_i = |S_i|. Using the concept of insertible vertices and the concept of neighborhood intersections, we prove the following theorem.     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

Cubic vertex‐transitive graphs of order 2pq

A graph is vertex?transitive or symmetric if its automorphism group acts transitively on vertices or ordered adjacent pairs of vertices of the graph, respectively. Let G be a finite group and S a subset of G such that 1?S and S={s^?1 | s∈S}. The Cayleygraph Cay(G, S) on G with respect to S is defined as the graph with vertex set G and edge set {{g, sg} | g∈G, s∈S}. Feng and Kwak [J Combin Theory B 97 (2007), 627–646; J Austral Math Soc 81 (2006), 153–164] classified all cubic symmetric graphs of order 4p or 2p² and in this article we classify all cubic symmetric graphs of order 2pq, where p and q are distinct odd primes. Furthermore, a classification of all cubic vertex‐transitive non‐Cayley graphs of order 2pq, which were investigated extensively in the literature, is given. As a result, among others, a classification of cubic vertex‐transitive graphs of order 2pq can be deduced. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 285–302, 2010     

Independence Sequences of Well-Covered Graphs: Non-Unimodality and the Roller-Coaster Conjecture

A graph G is well-covered provided each maximal independent set of vertices has the same cardinality. The term s_k of the independence sequence (s₀,s₁,,s) equals the number of independent k-sets of vertices of G. We investigate constraints on the linear orderings of the terms of the independence sequence of well-covered graphs. In particular, we provide a counterexample to the recent unimodality conjecture of Brown, Dilcher, and Nowakowski. We formulate the Roller-Coaster Conjecture to describe the possible linear orderings of terms of the independence sequence. We are grateful to Jason Brown for a helpful discussion in December of 1999 and to Richard Stanley for valuable feedback in August of 2000. The work of the second author was partially supported by the Naval Academy Research Council and ONR grant N0001400WR20041     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Inequality of Nordhaus-Gaddum type for total outer-connected domination in graphs

A set S of vertices in a graph G = (V, E) without isolated vertices is a total outer-connected dominating set (TCDS) of G if S is a total dominating set of G and G[V − S] is connected. The total outer-connected domination number of G, denoted by γ _tc (G), is the minimum cardinality of a TCDS of G. For an arbitrary graph without isolated vertices, we obtain the upper and lower bounds on γ _tc (G) + γ _tc ($ \bar G $ \bar G ), and characterize the extremal graphs achieving these bounds.     

Some Bistar Bipartite Ramsey Numbers

For bipartite graphs G ₁, G ₂, . . . ,G _k , the bipartite Ramsey number b(G ₁, G ₂, . . . , G _k ) is the least positive integer b so that any colouring of the edges of K _b,b with k colours will result in a copy of G _i in the ith colour for some i. A tree of diameter three is called a bistar, and will be denoted by B(s, t), where s ≥ 2 and t ≥ 2 are the degrees of the two support vertices. In this paper we will obtain some exact values for b(B(s, t), B(s, t)) and b(B(s, s), B(s, s)). Furtermore, we will show that if k colours are used, with k ≥ 2 and s ≥ 2, then \({b_{k}(B(s, s)) \leq \lceil k(s - 1) + \sqrt{(s - 1)^{2}(k^{2} - k) - k(2s - 4)} \rceil}\) . Finally, we show that for s ≥ 3 and k ≥ 2, the Ramsey number \({r_{k}(B(s, s)) \leq \lceil 2k(s - 1)+ \frac{1}{2} + \frac{1}{2} \sqrt{(4k(s - 1) + 1)^{2} - 8k(2s^{2} - s - 2)} \rceil}\) .     

On a Spanning Tree with Specified Leaves

Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting any two vertices. Dedicated to Professor Hikoe Enomoto on his 60th birthday.     

Resolvability in circulant graphs

A set W of the vertices of a connected graph G is called a resolving set for G if for every two distinct vertices u, v ∈ V (G) there is a vertex w ∈ W such that d(u, w) ≠ d(v, w). A resolving set of minimum cardinality is called a metric basis for G and the number of vertices in a metric basis is called the metric dimension of G, denoted by dim(G). For a vertex u of G and a subset S of V (G), the distance between u and S is the number min s∈S d(u, s). A k-partition Π = {S 1 , S 2 , . . . , S k } of V (G) is called a resolving partition if for every two distinct vertices u, v ∈ V (G) there is a set S i in Π such that d(u, Si )≠ d(v, Si ). The minimum k for which there is a resolving k-partition of V (G) is called the partition dimension of G, denoted by pd(G). The circulant graph is a graph with vertex set Zn , an additive group of integers modulo n, and two vertices labeled i and j adjacent if and only if i-j (mod n) ∈ C , where CZn has the property that C =-C and 0 ■ C. The circulant graph is denoted by Xn, Δ where Δ = |C|. In this paper, we study the metric dimension of a family of circulant graphs Xn, 3 with connection set C = {1, n/2 , n-1} and prove that dim(Xn, 3 ) is independent of choice of n by showing that dim(Xn, 3 ) ={3 for all n ≡ 0 (mod 4), 4 for all n ≡ 2 (mod 4). We also study the partition dimension of a family of circulant graphs Xn,4 with connection set C = {±1, ±2} and prove that pd(Xn, 4 ) is independent of choice of n and show that pd(X5,4 ) = 5 and pd(Xn,4 ) ={3 for all odd n ≥ 9, 4 for all even n ≥ 6 and n = 7.