Classification of amply regular graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>1</Subscript> = 6

An undirected graph with v vertices in which the degrees of all vertices are equal to k, each edge is contained in exactly λ triangles, and the intersection of the neighborhoods of any two vertices at distance 2 contains exactly µ vertices is called amply regular with parameters (v, k, λ, µ). We complete the classification of amply regular graphs with b ₁ = 6, where b ₁ = k ? λ ? 1.     

Distance-Regular Shilla Graphs with <Emphasis Type="Italic">b</Emphasis><Subscript>2</Subscript> = <Emphasis Type="Italic">c</Emphasis><Subscript>2</Subscript>

A Shilla graph is defined as a distance-regular graph of diameter 3 with second eigen-value θ₁ equal to a₃. For a Shilla graph, let us put a = a₃ and b = k/a. It is proved in this paper that a Shilla graph with b₂ = c₂ and noninteger eigenvalues has the following intersection array:

$$\left\{ {\frac{{{b^2}\left( {b - 1} \right)}}{2},\frac{{\left( {b - 1} \right)\left( {{b^2} - b + 2} \right)}}{2},\frac{{b\left( {b - 1} \right)}}{4};1,\frac{{b\left( {b - 1} \right)}}{4},\frac{{b{{\left( {b - 1} \right)}^2}}}{2}} \right\}$$

If Γ is a Q-polynomial Shilla graph with b₂ = c₂ and b = 2r, then the graph Γ has intersection array

$$\left\{ {2tr\left( {2r + 1} \right),\left( {2r + 1} \right)\left( {2rt + t + 1} \right),r\left( {r + t} \right);1,r\left( {r + t} \right),t\left( {4{r^2} - 1} \right)} \right\}$$

and, for any vertex u in Γ, the subgraph Γ₃(u) is an antipodal distance-regular graph with intersection array

$$\left\{ {t\left( {2r + 1} \right),\left( {2r - 1} \right)\left( {t + 1} \right),1;1,t + 1,t\left( {2r + 1} \right)} \right\}$$

The Shilla graphs with b₂ = c₂ and b = 4 are also classified in the paper.

     

Degree sum of a pair of independent edges and <Emphasis Type="Italic">Z</Emphasis><Subscript>3</Subscript>-connectivity

Let G be a 2-edge-connected simple graph on n vertices. For an edge e = uv ∈ E(G), define d(e) = d(u) + d(v). Let F denote the set of all simple 2-edge-connected graphs on n ≥ 4 vertices such that G ∈ F if and only if d(e) + d(e’) ≥ 2n for every pair of independent edges e, e’ of G. We prove in this paper that for each G ∈ F, G is not Z ₃-connected if and only if G is one of K _2,n?2, K _3,n?3, K _2,n?2 ⁺ , K _3,n?3 ⁺ or one of the 16 specified graphs, which generalizes the results of X. Zhang et al. [Discrete Math., 2010, 310: 3390–3397] and G. Fan and X. Zhou [Discrete Math., 2008, 308: 6233–6240].     

Neighbor sum distinguishing total chromatic number of <Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-minor free graph

A k-total coloring of a graph G is a mapping ?: V (G) ? E(G) → {1; 2,..., k} such that no two adjacent or incident elements in V (G) ? E(G) receive the same color. Let f(v) denote the sum of the color on the vertex v and the colors on all edges incident with v: We say that ? is a k-neighbor sum distinguishing total coloring of G if f(u) 6 ≠ f(v) for each edge uv ∈ E(G): Denote χ _Σ ^″ (G) the smallest value k in such a coloring of G: Pil?niak and Wo?niak conjectured that for any simple graph with maximum degree Δ(G), χ _Σ ^″ ≤ Δ(G)+3. In this paper, by using the famous Combinatorial Nullstellensatz, we prove that for K ₄-minor free graph G with Δ(G) > 5; χ _Σ ^″ = Δ(G) + 1 if G contains no two adjacent Δ-vertices, otherwise, χ _Σ ^″ (G) = Δ(G) + 2.     

<Emphasis Type="Italic">K</Emphasis><Subscript>4</Subscript>-free subgraphs of random graphs revisited

In Combinatorica 17(2), 1997, Kohayakawa, ?uczak and Rödl state a conjecture which has several implications for random graphs. If the conjecture is true, then, for example, an application of a version of Szemerédi’s regularity lemma for sparse graphs yields an estimation of the maximal number of edges in an H-free subgraph of a random graph G _{n, p} . In fact, the conjecture may be seen as a probabilistic embedding lemma for partitions guaranteed by a version of Szemerédi’s regularity lemma for sparse graphs. In this paper we verify the conjecture for H = K ₄, thereby providing a conceptually simple proof for the main result in the paper cited above.     

3-Connected {<Emphasis Type="Italic">K</Emphasis><Subscript>1,3</Subscript>, <Emphasis Type="Italic">P</Emphasis><Subscript>9</Subscript>}-Free Graphs are Hamiltonian-Connected

We investigate pairs of forbidden subgraphs that imply a 3-connected graph is Hamiltonian-connected. In particular we show that the pair {K _1,3, P ₉} is such a pair. As it is known that P ₁₀ cannot replace P ₉, this result is best possible. Further, we show that certain other graphs are not possible.     

Automorphisms of Coxeter groups of type <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

A Coxeter system (W, S) is said to be of type K _n if the associated Coxeter graph Γ_S is complete on n vertices and has only odd edge labels. If W satisfies either of: (1) n = 3; (2) W is rigid; then the automorphism group of W is generated by the inner automorphisms of W and any automorphisms induced by Γ_S. Indeed, Aut(W) is the semidirect product of Inn(W) and the group of diagram automorphisms, and furthermore W is strongly rigid. We also show that if W is a Coxeter group of type K _n then W has exactly one conjugacy class of involutions and hence Aut(W) = Spec(W).     

Some class 1 graphs on <Emphasis Type="Italic">g</Emphasis><Subscript><Emphasis Type="Italic">c</Emphasis></Subscript>-colorings

An edge-coloring of a graph G is an assignment of colors to all the edges of G. A g _c -coloring of a graph G is an edge-coloring of G such that each color appears at each vertex at least g(v) times. The maximum integer k such that G has a g _c -coloring with k colors is called the g _c -chromatic index of G and denoted by \(\chi\prime_{g_{c}}\)(G). In this paper, we extend a result on edge-covering coloring of Zhang and Liu in 2011, and give a new sufficient condition for a simple graph G to satisfy \(\chi\prime_{g_{c}}\)(G) = δ _g (G), where \(\delta_{g}\left(G\right) = min_{v\epsilon V (G)}\left\{\lfloor\frac{d\left(v\right)}{g\left(v\right)}\rfloor\right\}\).     

Regular maps of graphs of order 4<Emphasis Type="Italic">p</Emphasis>

A 2-cell embedding f : X → S of a graph X into a closed orientable surface S can be described combinatorially by a pair M = (X;ρ ) called a map, where ρ is a product of disjoint cycle permutations each of which is the permutation of the arc set of X initiated at the same vertex following the orientation of S . It is well known that the automorphism group of M acts semi-regularly on the arc set of X and if the action is regular, then the map M and the embedding f are called regular. Let p and q be primes. Du et al. [J. Algebraic Combin., 19, 123-141 (2004)] classified the regular maps of graphs of order pq . In this paper all pairwise non-isomorphic regular maps of graphs of order 4 p are constructed explicitly and the genera of such regular maps are computed. As a result, there are twelve sporadic and six infinite families of regular maps of graphs of order 4 p ; two of the infinite families are regular maps with the complete bipartite graphs K2p,2p as underlying graphs and the other four infinite families are regular balanced Cayley maps on the groups Z4p , Z22 × Zp and D4p .     

Recognition of the groups <Emphasis Type="Italic">E</Emphasis><Subscript>7</Subscript>(2) and <Emphasis Type="Italic">E</Emphasis><Subscript>7</Subscript>(3) by prime graph

It is proved that the groups E ₇(2) and E ₇(3) are recognizable by their prime graphs. As a corollary, this completes the proof of V.D. Mazurov’s conjecture that every finite simple group whose prime graph has at least three connected components is either recognizable by spectrum or isomorphic to A ₆.     

On <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis>,<Emphasis Type="Italic">q</Emphasis></Subscript>-factorization of complete bipartite multigraphs

Let λK _m,n be a complete bipartite multigraph with two partite sets having m and n vertices, respectively. A K _p,q -factorization of λK _m,n is a set of edge-disjoint K _p,q -factors of λK _m,n which partition the set of edges of λK _m,n . When p = 1 and q is a prime number, Wang, in his paper [On K _1,q -factorization of complete bipartite graph, Discrete Math., 126: (1994), 359-364], investigated the K _1,q -factorization of K _m,n and gave a sufficient condition for such a factorization to exist. In papers [K _1,k -factorization of complete bipartite graphs, Discrete Math., 259: 301-306 (2002),; K _p,q -factorization of complete bipartite graphs, Sci. China Ser. A-Math., 47: (2004), 473-479], Du and Wang extended Wang’s result to the case that p and q are any positive integers. In this paper, we give a sufficient condition for λK _m,n to have a K _p,q -factorization. As a special case, it is shown that the necessary condition for the K _p,q -factorization of λK _m,n is always sufficient when p : q = k : (k + 1) for any positive integer k.     

On <Emphasis Type="Italic">g</Emphasis><Subscript><Emphasis Type="Italic">c</Emphasis></Subscript>-colorings of nearly bipartite graphs

Let G be a simple graph, let d(v) denote the degree of a vertex v and let g be a nonnegative integer function on V (G) with 0 ≤ g(v) ≤ d(v) for each vertex v ∈ V (G). A g _c -coloring of G is an edge coloring such that for each vertex v ∈ V (G) and each color c, there are at least g(v) edges colored c incident with v. The g _c -chromatic index of G, denoted by χ′g _c (G), is the maximum number of colors such that a gc-coloring of G exists. Any simple graph G has the g _c -chromatic index equal to δ _g (G) or δ _g (G) ? 1, where \({\delta _g}\left( G \right) = \mathop {\min }\limits_{v \in V\left( G \right)} \left\lfloor {d\left( v \right)/g\left( v \right)} \right\rfloor \). A graph G is nearly bipartite, if G is not bipartite, but there is a vertex u ∈ V (G) such that G ? u is a bipartite graph. We give some new sufficient conditions for a nearly bipartite graph G to have χ′g _c (G) = δ _g (G). Our results generalize some previous results due to Wang et al. in 2006 and Li and Liu in 2011.     

Quasirecognition by prime graph of <Emphasis Type="Italic">L</Emphasis><Subscript>10</Subscript>(2)

Let G be a finite group. The prime graph of G is denoted by Γ(G). The main result we prove is as follows: If G is a finite group such that Γ(G) = Γ(L ₁₀(2)) then G/O ₂(G) is isomorphic to L ₁₀(2). In fact we obtain the first example of a finite group with the connected prime graph which is quasirecognizable by its prime graph. As a consequence of this result we can give a new proof for the fact that the simple group L ₁₀(2) is uniquely determined by the set of its element orders.     

On <Emphasis Type="Italic">K</Emphasis><Subscript>1,3</Subscript>-free strictly Deza graphs

A graph on v vertices is called a Deza graph with parameters (v, k, b, a) if it is k-regular and the number of common neighbors of two distinct vertices takes on one of two values. We describe strictly Deza graphs that do not contain K _1,3 among their induced subgraphs and are unions of closed neighborhoods of two nonadjacent vertices. The latter condition means that there are two nonadjacent vertices such that any other vertex is adjacent to at least one of the them.     

Strongly regular locally <Emphasis Type="Italic">GQ</Emphasis>(4,<Emphasis Type="Italic">t</Emphasis>)-graphs

Amply regular with parameters (v, k, λ, μ) we call an undirected graph with v vertices in which the degrees of all vertices are equal to k, every edge belongs to λ triangles, and the intersection of the neighborhoods of every pair of vertices at distance 2 contains exactly μ vertices. An amply regular diameter 2 graph is called strongly regular. We prove the nonexistence of amply regular locally GQ(4,t)-graphs with (t,μ) = (4, 10) and (8, 30). This reduces the classification problem for strongly regular locally GQ(4,t)-graphs to studying locally GQ(4, 6)-graphs with parameters (726, 125, 28, 20).     

Planar Graded Lattices and the <Emphasis Type="Bold">c</Emphasis><Subscript>1</Subscript>-Median Property

Let L be a lattice of finite length, ξ = (x ₁,…, x _k )∈L ^k , and y ∈ L. The remoteness r(y, ξ) of y from ξ is d(y, x ₁)+?+d(y, x _k ), where d stands for the minimum path length distance in the covering graph of L. Assume, in addition, that L is a graded planar lattice. We prove that whenever r(y, ξ) ≤ r(z, ξ) for all z ∈ L, then y ≤ x ₁∨?∨x _k . In other words, L satisfies the so-called c ₁ -median property.     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

Small <Emphasis Type="Italic">AT</Emphasis>4-graphs and strongly regular subgraphs corresponding to them

Let M be the class of strongly regular graphs for which μ is a nonprincipal eigenvalue. Note that the neighborhood of any vertex of an AT4-graph lies in M. Parameters of graphs from M were described earlier. We find intersection arrays of small AT4-graphs and of strongly regular graphs corresponding to them.     

New characterization of <Emphasis Type="Italic">S</Emphasis><Subscript>4</Subscript>(<Emphasis Type="Italic">q</Emphasis>) by its noncommuting graph

Let G be a nonabelian group, and associate the noncommuting graph ?(G) with G as follows: the vertex set of ?(G) is G\Z(G) with two vertices x and y joined by an edge whenever the commutator of x and y is not the identity. Let S ₄(q) be the projective symplectic simple group, where q is a prime power. We prove that if G is a group with ?(G) ? ?(S ₄(q)) then G ? S ₄(q).     

Obstructions to the uniform stability of a <Emphasis Type="Italic">C</Emphasis><Subscript>0</Subscript>-semigroup

Let T _t : X → X be a C ₀-semigroup with generator A. We prove that if the abscissa of uniform boundedness of the resolvent s ₀(A) is greater than zero then for each nondecreasing function h(s): ?₊ → R ₊ there are x′ ∈ X′ and x ∈ X satisfying ∫ ₀ ^∞ h(|〈x′, T _x x〉|)dt = ∞. If i? ∩ Sp(A) ≠ Ø then such x may be taken in D(A ^∞).