Group Connectivity of Bridged Graphs

Let G be a 2-edge-connected simple graph, and let A denote an abelian group with the identity element 0. If a graph G ^* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say G can be A-reduced to G*. A graph G is bridged if every cycle of length at least 4 has two vertices x, y such that d _G (x, y) < d _C (x, y). In this paper, we investigate the group connectivity number Λ _g (G) = min{n: G is A-connected for every abelian group with |A| ≥ n} for bridged graphs. Our results extend the early theorems for chordal graphs by Lai (Graphs Comb 16:165–176, 2000) and Chen et al. (Ars Comb 88:217–227, 2008).     

Group connectivity and group colorings of graphs — A survey

In 1950s, Tutte introduced the theory of nowhere-zero flows as a tool to investigate the coloring problem of maps, together with his most fascinating conjectures on nowhere-zero flows. These have been extended by Jaeger et al. in 1992 to group connectivity, the nonhomogeneous form of nowhere-zero flows. Let G be a 2-edge-connected undirected graph, A be an (additive) abelian group and A* = A − {0}. The graph G is A-connected if G has an orientation D(G) such that for every map b: V (G) ↦ A satisfying Σ _v∈V(G) b(v) = 0, there is a function f: E(G) ↦ A* such that for each vertex v ∈ V (G), the total amount of f-values on the edges directed out from v minus the total amount of f-values on the edges directed into v is equal to b(v). The group coloring of a graph arises from the dual concept of group connectivity. There have been lots of investigations on these subjects. This survey provides a summary of researches on group connectivity and group colorings of graphs. It contains the following sections.

Group connectivity in line graphs

Tutte introduced the theory of nowhere zero flows and showed that a plane graph G has a face k-coloring if and only if G has a nowhere zero A-flow, for any Abelian group A with |A|≥k. In 1992, Jaeger et al. [9] extended nowhere zero flows to group connectivity of graphs: given an orientation D of a graph G, if for any b:V(G)?A with ∑_v∈V(G)b(v)=0, there always exists a map f:E(G)?A−{0}, such that at each v∈V(G), in A, then G is A-connected. Let Z₃ denote the cyclic group of order 3. In [9], Jaeger et al. (1992) conjectured that every 5-edge-connected graph is Z₃-connected. In this paper, we proved the following.

• (i) 

  Every 5-edge-connected graph is Z3-connected if and only if every 5-edge-connected line graph is Z3-connected.

• (ii) 

  Every 6-edge-connected triangular line graph is Z3-connected.

• (iii) 

  Every 7-edge-connected triangular claw-free graph is Z3-connected.

In particular, every 6-edge-connected triangular line graph and every 7-edge-connected triangular claw-free graph have a nowhere zero 3-flow.     

How Tight Is the Bollobás-Komlós Conjecture?

The bipartite case of the Bollobás and Komlós conjecture states that for every j₀, %>0 there is an !=!(j₀, %) >0 such that the following statement holds: If G is any graph with minimum degree at least n$\displaystyle {n \over 2}+%n then G contains as subgraphs all n vertex bipartite graphs, H, satisfying¶H)hj₀ \quad {\rm and} \quad b(H)h!n.$j (H)hj₀ \quad {\rm and} \quad b(H)h!n.¶Here b(H), the bandwidth of H, is the smallest b such that the vertices of H can be ordered as v₁, …, v_n such that v_i~_Hv_j implies |imj|hb.¶ This conjecture has been proved in [1]. Answering a question of E. Szemerédi [6] we show that this conjecture is tight in the sense that as %̂ then !̂. More precisely, we show that for any 0 such that that !(j₀, %)Д %.     

The 2-Pebbling Property and a Conjecture of Graham's

The pebbling number of a graph G, f(G), is the least m such that, however m pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. It is conjectured that for all graphs G and H, f(G 2H)hf(G)f(H).¶Let C_m and C_n be cycles. We prove that f(C_m 2C_n)hf(C_m) f(C_n) for all but a finite number of possible cases. We also prove that f(G2T)hf(G) f(T) when G has the 2-pebbling property and T is any tree.     

Degree conditions for group connectivity

Let G be a 2-edge-connected simple graph on n≥13 vertices and A an (additive) abelian group with |A|≥4. In this paper, we prove that if for every uv∉E(G), max{d(u),d(v)}≥n/4, then either G is A-connected or G can be reduced to one of K_2,3,C₄ and C₅ by repeatedly contracting proper A-connected subgraphs, where C_k is a cycle of length k. We also show that the bound n≥13 is the best possible.     

All 4-Edge-Connected HHD-Free Graphs are {\mathbb{Z}_3}-Connected

An undirected graph G = (V, E) is called \mathbbZ₃{\mathbb{Z}_3}-connected if for all b: V ? \mathbbZ₃{b: V \rightarrow \mathbb{Z}_3} with ?_{v ? V}b(v)=0{\sum_{v \in V}b(v)=0}, an orientation D = (V, A) of G has a \mathbbZ₃{\mathbb{Z}_3}-valued nowhere-zero flow f: A? \mathbbZ₃-{0}{f: A\rightarrow \mathbb{Z}_3-\{0\}} such that ?_{e ? d⁺(v)}f(e)-?_{e ? d^-(v)}f(e)=b(v){\sum_{e \in \delta^+(v)}f(e)-\sum_{e \in \delta^-(v)}f(e)=b(v)} for all v ? V{v \in V}. We show that all 4-edge-connected HHD-free graphs are \mathbbZ₃{\mathbb{Z}_3}-connected. This extends the result due to Lai (Graphs Comb 16:165–176, 2000), which proves the \mathbbZ₃{\mathbb{Z}_3}-connectivity for 4-edge-connected chordal graphs.     

Group connectivity of complementary graphs

Let G be a 2‐edge‐connected undirected graph, A be an (additive) abelian group and A* = A?{0}. A graph G is A‐connected if G has an orientation D(G) such that for every function b: V(G)?A satisfying , there is a function f: E(G)?A* such that for each vertex v∈V(G), the total amount of f values on the edges directed out from v minus the total amount of f values on the edges directed into v equals b(v). For a 2‐edge‐connected graph G, define Λ_g(G) = min{k: for any abelian group A with |A|?k, G is A‐connected }. In this article, we prove the following Ramsey type results on group connectivity:

1. Let G be a simple graph on n?6 vertices. If min{δ(G), δ(G^c)}?2, then either Λ_g(G)?4, or Λ_g(G^c)?4.
2. Let Z₃ denote the cyclic group of order 3, and G be a simple graph on n?44 vertices. If min{δ(G), δ(G^c)}?4, then either G is Z₃‐connected, or G^c is Z₃‐connected. © 2011 Wiley Periodicals, Inc. J Graph Theory

     

On 3-Edge-Connected Supereulerian Graphs

The supereulerian graph problem, raised by Boesch et al. (J Graph Theory 1:79–84, 1977), asks when a graph has a spanning eulerian subgraph. Pulleyblank showed that such a decision problem, even when restricted to planar graphs, is NP-complete. Jaeger and Catlin independently showed that every 4-edge-connected graph has a spanning eulerian subgraph. In 1992, Zhan showed that every 3-edge-connected, essentially 7-edge-connected graph has a spanning eulerian subgraph. It was conjectured in 1995 that every 3-edge-connected, essentially 5-edge-connected graph has a spanning eulerian subgraph. In this paper, we show that if G is a 3-edge-connected, essentially 4-edge-connected graph and if for every pair of adjacent vertices u and v, d _G (u) + d _G (v) ≥ 9, then G has a spanning eulerian subgraph.     

Wilson's functional equation on P3-groups

Summary. Consider Wilson's functional equation¶¶f(xy) + f(xy^-1) = 2f(f)g(y) f(xy) + f(xy^{-1}) = 2f(f)g(y) , for f,g : G ? K f,g : G \to K ¶where G is a group and K a field with char K 1 2 {\rm char}\, K\ne 2 .¶Aczél, Chung and Ng in 1989 have solved Wilson's equation, assuming that the function g satisfies Kannappan's condition g(xyz) = g(xzy) and f(xy) = f(yx) for all x,y,z ? G x,y,z\in G .¶In the present paper we obtain the general solution of Wilson's equation when G is a P₃-group and we show that there exist solutions different of those obtained by Aczél, Chung and Ng.¶A group G is said to be a P₃-group if the commutator subgroup G' of G, generated by all commutators [x,y] := x^-1y^-1xy, has the order one or two.     

A wavelike functional equation of Pexider type

Summary. Let (G, +) and (H, +) be abelian groups such that the equation 2u = v 2u = v is solvable in both G and H. It is shown that if f₁, f₂, f₃, f₄, : G ×G ? H f_1, f_2, f_3, f_4, : G \times G \longrightarrow H satisfy the functional equation f₁(x + t, y + s) + f₂(x - t, y - s) = f₃(x + s, y - t) + f₄(x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , then f₁, f₂, f₃, and f₄ are given by f₁ = w + h, f₂ = w - h, f₃ = w + k, f₄ = w - k where w : G ×G ? H w : G \times G \longrightarrow H is an arbitrary solution of f (x + t, y + s) + f (x - t, y - s) = f (x + s, y - t) + f (x - s, y + t) for all x, y, s, t ? G x, y, s, t \in G , and h, k : G ×G ? H h, k : G \times G \longrightarrow H are arbitrary solutions of D_y,t³g(x,y) = 0 \Delta_{y,t}^{3}g(x,y) = 0 and D_x,t³g(x,y) = 0 \Delta_{x,t}^{3}g(x,y) = 0 for all x, y, s, t ? G x, y, s, t \in G .     

On Solvability of Finite Groups with Few Non-Normal Subgroups

For a finite group G, let v(G) denote the number of conjugacy classes of non-normal subgroups of G and vc(G) denote the number of conjugacy classes of non-normal noncyclic subgroups of G. In this paper, we show that every finite group G satisfying v(G) ≤2|π(G)| or vc(G) ≤ |π(G)| is solvable, and for a finite nonsolvable group G, v(G) = 2|π(G)| +1 if and only if G ? A ₅.     

Neighborhood Unions and Z 3-Connectivity in Graphs

Let G be a 2-edge-connected simple graph on n ≥ 14 vertices, and let A be an abelian group with the identity element 0. If a graph G* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say that G can be A-reduced to G*. In this paper, we prove that if for every ${uv\not\in E(G), |N(u) \cup N(v)| \geq \lceil \frac{2n}{3} \rceil}$ , then G is not Z ₃-connected if and only if G can be Z ₃-reduced to one of ${\{C_3,K_4,K_4^-, L\}}$ , where L is obtained from K ₄ by adding a new vertex which is joined to two vertices of K ₄.     

Auto-equivalences of derived categories acting on cohomology

Let A be a k-algebra which is projective as a k-module, let M be an A-module whose endomorphisms are given by multiplication by central elements of A, and let TrPic_k(A) be the group of standard self-equivalences of the derived category of bounded complexes of A-modules. Then we define an action of the stabilizer of M in TrPic_k(A) on the Ext-algebra of M. In case M is the trivial module for the group algebra kG = A, this defines an action on the cohomology ring of G which extends the well-known action of the automorphism group of G on the cohomology group.     

Connectivity of iterated line graphs

Let k≥0 be an integer and L^k(G) be the kth iterated line graph of a graph G. Niepel and Knor proved that if G is a 4-connected graph, then κ(L²(G))≥4δ(G)−6. We show that the connectivity of G can be relaxed. In fact, we prove in this note that if G is an essentially 4-edge-connected and 3-connected graph, then κ(L²(G))≥4δ(G)−6. Similar bounds are obtained for essentially 4-edge-connected and 2-connected (1-connected) graphs.     

Independent Trees in Planar Graphs Independent trees

We prove the following statement: Let G be a finite k-connected undirected planar graph and s be a vertex of G. Then there exist k spanning trees T₁,…,T_k in G such that for each vertex xps of G, the k paths from x to s in T₁,…,T_k are pairwise openly disjoint.     

A linear functional equation with a singularity at a fixed point

Summary. Local solutions of the functional equation¶¶z^k f( z) = ?_k=1ⁿG_k( z) f( s_kz ) +g( z) z{^\kappa} \phi \left( z\right) =\sum_{k=1}^nG_k\left( z\right) \phi \left( s_kz \right) +g\left( z\right) ¶with k > 0 \kappa > 0 and | s_k| \gt 1 \left| s_k\right| \gt 1 are considered. We prove that the equation is solvable if and only if a certain system of k \kappa conditions on G_k (k = 1, 2, ... , n) and g is fulfilled.     

Group Connectivity in 3-Edge-Connected Graphs

Let A be an abelian group with |A|?≥ 4. For integers k and l with k?>?0 and l?≥ 0, let ${{\mathcal C}(k, l)}$ denote the family of 2-edge-connected graphs G such that for each edge cut ${S\subseteq E(G)}$ with two or three edges, each component of G ? S has at least (|V(G)| ? l)/k vertices. In this paper, we show that if G is 3-edge-connected and ${G\in {\mathcal C}(6,5)}$ , then G is not A-connected if and only if G can be A-reduced to the Petersen graph.     

Labeling bipartite permutation graphs with a condition at distance two

An L(p,q)-labeling of a graph G is an assignment f from vertices of G to the set of non-negative integers {0,1,…,λ} such that |f(u)−f(v)|≥p if u and v are adjacent, and |f(u)−f(v)|≥q if u and v are at distance 2 apart. The minimum value of λ for which G has L(p,q)-labeling is denoted by λ_p,q(G). The L(p,q)-labeling problem is related to the channel assignment problem for wireless networks.In this paper, we present a polynomial time algorithm for computing L(p,q)-labeling of a bipartite permutation graph G such that the largest label is at most (2p−1)+q(bc(G)−2), where bc(G) is the biclique number of G. Since λ_p,q(G)≥p+q(bc(G)−2) for any bipartite graph G, the upper bound is at most p−1 far from optimal.     

On matrix near-rings

Let R be a right near-ring with identity and M_n(R) be the near-ring of n 2 n matrices over R in the sense of Meldrum and Van der Walt. In this paper, M_n(R) is said to be s\sigma-generated if every n 2 n matrix A over R can be expressed as a sum of elements of X_n(R), where X_n(R)={f_ij^r | 1\leqq i, j\leqq n, r ? R}X_n(R)=\{f_{ij}^r\,|\,1\leqq i, j\leqq n, r\in R\}, is the generating set of M_n(R). We say that R is s\sigma-generated if M_n(R) is s\sigma-generated for every natural number n. The class of s\sigma-generated near-rings contains distributively generated and abstract affine near-rings. It is shown that this class admits homomorphic images. For abelian near-rings R, we prove that the zerosymmetric part of R is a ring, so the class of zerosymmetric abelian s\sigma-generated near-rings coincides with the class of rings. Further, for every n, there is a bijection between the two-sided subgroups of R and those of M_n(R).