On the average genus of a graph

Not all rational numbers are possibilities for the average genus of an individual graph. The smallest such numbers are determined, and varied examples are constructed to demonstrate that a single value of average genus can be shared by arbitrarily many different graphs. It is proved that the number 1 is a limit point of the set of possible values for average genus and that the complete graph K₄ is the only 3-connected graph whose average genus is less than 1.     

On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.     

The average Steiner distance of a graph

The average distance μ(G) of a graph G is the average among the distances between all pairs of vertices in G. For n ≥ 2, the average Steiner n-distance μ_n(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, μ_n(G) ≤ μ_k(G) + μ_n+1−k(G) where 2 ≤ k ≤ n − 1. The range for the average Steiner n-distance of a connected graph G in terms of n and |V(G)| is established. Moreover, for a tree T and integer k, 2 ≤ k ≤ n − 1, it is shown that μ_n(T) ≤ (n/k)μ_k(T) and the range for μ_n(T) in terms of n and |V(T)| is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined. © 1996 John Wiley & Sons, Inc.     

Lower bounds for the average genus

Two lower bounds are obtained for the average genus of graphs. The average genus for a graph of maximum valence at most 3 is at least half its maximum genus, and the average genus for a 2-connected simplicial graph other than a cycle is at least 1/16 of its cycle rank. © 1995 John Wiley & Sons, Inc.     

An additivity theorem for maximum genus of a graph

Let G be a finite, connected graph with no loops or multiple edges. If G is the union of two blocks, then a necessary and sufficient condition is given for the maximum genus of G to be the sum of the maximum genera of its blocks. If in addition the blocks of G are upper embeddable, then a necessary and sufficient condition is given for the upper embeddability of G.     

On the average crosscap number Ⅱ: Bounds for a graph

The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less than 2β(G)-1/2β(G)-1β(G)β(G) and not larger than/β(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number.     

On the average crosscap number II: Bounds for a graph

The bounds are obtained for the average crosscap number. Let G be a graph which is not a tree. It is shown that the average crosscap number of G is not less thanβ(G)-1/2β(G)-1β(G) and not larger thanβ(G). Furthermore, we also describe the structure of the graphs which attain the bounds of the average crosscap number.     

The genus of a type of graph

Based on the joint tree model introduced by Liu, the genera of further types of graphs not necessary to have certain symmetry can be obtained. In this paper, we obtain the genus of a new type of graph with weak symmetry. As a corollary, the genus of complete tripartite graph K n,n,l (l≥n≥2) is also derived. The method used here is more direct than those methods, such as current graph, used to calculate the genus of a graph and can be realized in polynomial time.     

On the genus of a random graph

Let p = p(n) be a function of n with 0<p<1. We consider the random graph model ??(n, p); that is, the probability space of simple graphs with vertex-set {1, 2,…, n}, where two distinct vertices are adjacent with probability p. and for distinct pairs these events are mutually independent. Archdeacon and Grable have shown that if p²(1 ? p²) ?? 8(log n)⁴/n. then the (orientable) genus of a random graph in ??(n, p) is (1 + o(1))pn²/12. We prove that for every integer i ? 1, if n^?i/(i + 1) «p «n^{?(i ? 1)/i}. then the genus of a random graph in ??(n, p) is (1 + o(1))i/4(i + 2) pn². If p = cn^?(i?1)/o, where c is a constant, then the genus of a random graph in ??(n, p) is (1 + o(1))g(i, c, n)pn² for some function g(i, c, n) with 1/12 ? g(i, c, n) ? 1. but for i > 1 we were unable to compute this function.     

The average degree of a subcubic edge-chromatic critical graph

A graph is here called 3- critical if , and for every edge of . The 3-critical graphs include (the Petersen graph with a vertex deleted), and subcubic graphs that are Hajós joins of copies of . Building on a recent paper of Cranston and Rabern, it is proved here that if is 3-critical and not nor a Hajós join of two copies of , then has average degree at least ; this bound is sharp, as it is the average degree of a Hajós join of three copies of .     

The minimum genus of a two-point universal graph

A graph G is two-point universal if, given any two vertices A and B, there is a vertex jointed to both, a vertex joined to neither, a vertex joined to A but not B, and a vertex joined to B but not A. Erdös asked whether there is an infinite family of such graphs of some genus γ. In this note, we show that the number of vertices of a two-point universal graph of genus γ satisfies n ≤ 216(2γ + 1)² so that there are most finitely many of each genus.     

模糊联盟合作对策的平均树解

给出图对策中平均树解的拓展形式, 证明其是满足分支有效性和分支公平性的唯一解. 针对具有模糊联盟的图对策, 提出了一种模糊分配, 即模糊平均树解. 当模糊联盟图对策为完全图对策时, 模糊平均树解等于模糊Shapley值. 最后, 讨论了模糊平均树解与模糊联盟核心之间的关系, 并进行了实例论证.     

The maximum genus of a 3-regular simplicial graph

In this paper, the relationship between non-separating independent number and the maximum genus of a 3-regular simplicial graph is presented. A lower bound on the maximumgenus of a 3-regular graph invalving girth is provided. The lower bound is tight, it improves a bound of Huang and Liu.     

On the Euler genus of a 2-connected graph

The Euler genus of the surface Σ obtained from the sphere by the addition of k crosscaps and h handles is ε(Σ) = k + 2h. For a graph G, the Euler genus ε(G) of G is the smallest Euler genus among all surfaces in which G embeds. The following additivity theorem is proved.Theorem. Suppose G = H ∪ K, where H and K have exactly the vertices v and win common. Then ε(G) = min(ε(H + vw) + ε(K + vw), ε(H) + ε(K) + 2).     

Remarks on the lower bounds for the average genus

Let G be a graph of maximum degree at most four. By using the overlap matrix method which is introduced by B. Mohar, we show that the average genus of G is not less than 1/3 of its maximum genus, and the bound is best possible. Also, a new lower bound of average genus in terms of girth is derived.     

On the non-orientable genus of a 2-connected graph

In earlier works, additivity theorems for the genus and Euler genus of unions of graphs at two points have been given. In this work, the analogous result for the non-orientable genus is given. If Σ is obtained from the sphere by the addition of k>0 crosscaps, define γ(Σ) to be k. For a graph G, define γ(G) to be the least element in the set {γ(Σ) | G embeds in Σ}.Theorem. Let H₁ and H₂ be connected graphs such that H₁ ∩ H₂ consists of the isolated vertices v and w. Then, for some μ ϵ −1, 0, 1, 2, γ(H₁ ∪ H₂) = γ(H₁) + γ(H₂) + μ.A formula for μ is given.     

How to determine the maximum genus of a graph

The maximum genus, γ_M(G), of a connected graph G is the largest genus γ(S) for orientable surfaces S in which G has a 2-cell embedding. In this paper, we define a new combinatorial invariant ξ(G), the Betti deficiency of G, to be ξ(C) = min_C?G{ξ(C) 6 ξ(C) = number of odd components of a cotree C of G (by odd component we mean one with an odd number of edges). We formalize a new embedding technique to obtain the formula:

$\text{γ}{}_{\mathrm{M}}\text{(G)=}\text{1}\text{2}\text{(β(G)?ξ(G))}$

where β(G) denotes the Betti number of G.In a further paper, various consequences will be given.     

A short note about pursuit games played on a graph with a given genus

On a finite simple graph G = (X,E), p players pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ and one player evader B who move in turn along the edges of G are considered. The p pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ want to catch B who tries to escape. R. Nowakowski and P. Winkler [Discrete Math.43 (1983), 235–240] and A. Quilliot [“Thèse de 3° cycle,” pp. 131–145, Université de Paris VI, 1978] already characterized the graphs such that one pursuer is sufficient to catch the evader B. Very recently, M. Aigner and M. Fromme [Appl. Discrete Math., in press] proved that if G is a planar graph, three pursuers are sufficient to catch the evader B. This result is extended, showing that if G is a graph with a given genus k, then 3 + 2k pursuers are enough to “arrest” the evader B.