On integral Cayley sum graphs

Let S be a subset of a finite abelian group G. The Cayley sum graph Cay⁺(G, S) of G with respect to S is a graph whose vertex set is G and two vertices g and h are joined by an edge if and only if g + h ∈ S. We call a finite abelian group G a Cayley sum integral group if for every subset S of G, Cay⁺(G, S) is integral i.e., all eigenvalues of its adjacency matrix are integers. In this paper, we prove that all Cayley sum integral groups are represented by Z₃ and Zn₂ ⁿ, n ≥ 1, where Z_k is the group of integers modulo k. Also, we classify simple connected cubic integral Cayley sum graphs.     

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.     

An implicit degree condition for relative length of long paths and cycles in graphs

For a graph G, we denote by p(G) and c(G) the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id(v) denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n + 1, then either G contains a hamiltonian path, or c(G) ≥ p(G) ? 1.     

Minimum Difference Representations of Graphs

Define a k-minimum-difference-representation (k-MDR) of a graph G to be a family of sets \({\{S(v): v\in V(G)\}}\) such that u and v are adjacent in G if and only if min{|S(u)?S(v)|, |S(v)?S(u)|} ≥ k. Define ρ _min(G) to be the smallest k for which G has a k-MDR. In this note, we show that {ρ _min(G)} is unbounded. In particular, we prove that for every k there is an n ₀ such that for n > n ₀ ‘almost all’ graphs of order n satisfy ρ _min(G) > k. As our main tool, we prove a Ramsey-type result on traces of hypergraphs.     

The Local Metric Dimension of Strong Product Graphs

A vertex \(v\in V(G)\) is said to distinguish two vertices \(x,y\in V(G)\) of a nontrivial connected graph G if the distance from v to x is different from the distance from v to y. A set \(S\subset V(G)\) is a local metric generator for G if every two adjacent vertices of G are distinguished by some vertex of S. A local metric generator with the minimum cardinality is called a local metric basis for G and its cardinality, the local metric dimension of G. It is known that the problem of computing the local metric dimension of a graph is NP-Complete. In this paper we study the problem of finding exact values or bounds for the local metric dimension of strong product of graphs.     

On a problem of impulse control under interference

This paper contains several results about the structure of the congruence kernel C^(S)(G) of an absolutely almost simple simply connected algebraic group G over a global field K with respect to a set of places S of K. In particular, we show that C^(S)(G)) is always trivial if S contains a generalized arithmetic progression. We also give a criterion for the centrality of C^(S)(G) in the general situation in terms of the existence of commuting lifts of the groups G(K_v) for v ? S in the S-arithmetic completion ?^(S). This result enables one to give simple proofs of the centrality in a number of cases. Finally, we show that if K is a number field and G is K-isotropic, then C^(S)(G) as a normal subgroup of ?^(S) is almost generated by a single element.     

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).     

On Eccentric Connectivity Index of Eccentric Graph of Regular Dendrimer

The eccentric connectivity index \(\xi ^c(G)\) of a connected graph G is defined as \(\xi ^c(G) =\sum _{v \in V(G)}{deg(v) e(v)},\) where deg(v) is the degree of vertex v and e(v) is the eccentricity of v. The eccentric graph, \(G_e\), of a graph G has the same set of vertices as G,  with two vertices u, v adjacent in \(G_e\) if and only if either u is an eccentric vertex of v or v is an eccentric vertex of u. In this paper, we obtain a formula for the eccentric connectivity index of the eccentric graph of a regular dendrimer. We also derive a formula for the eccentric connectivity index for the second iteration of eccentric graph of regular dendrimer.     

Neighborhood contraction in graphs

Let G be a graph and v be any vertex of G. Then the neighborhood contracted graphG_v of G, with respect to the vertex v, is the graph with vertex set V ? N(v), where two vertices u,w ∈ V ? N(v) are adjacent in G_v if either w = v and u is adjacent to any vertex of N(v) in G or u,w ? N[v] and u,w are adjacent in G. The properties of the neighborhood contracted graphs are discussed in this paper. The neighborhood contraction in some special class of graphs, the domination in a graph and the neighborhood contracted graphs are discussed in the paper.     

Minimum implicit degree condition restricted to claws for hamiltonian cycles

Let id(v) denote the implicit degree of a vertex v in a graph G. We define G to be implicit 1-heavy (implicit 2-heavy) if at least one (two) of the end vertices of each induced claw has (have) implicit degree at least n/2. In this paper, we prove that: (a) Let G be a 2-connected graph of order n ≥ 3. If G is implicit 2-heavy and |N(u) ∩ N(v)| ≥ 2 for every pair of vertices u and v with d(u, v) = 2 and max{id(u), id(v)} < n/2, then G is hamiltonian. (b) Let G be a 3-connected graph of order n ≥ 3. If G is implicit 1-heavy and |N(u) ∩ N(v)| ≥ 2 for each pair of vertices u and v with d(u, v) = 2 and max{id(u), id(v)} < n/2, then G is hamiltonian.     

On <Emphasis Type="Italic">r</Emphasis>-recognition by prime graph of <Emphasis Type="Italic">B</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript>(3) where <Emphasis Type="Italic">p</Emphasis> is an odd prime

Let G be a finite group. The prime graph Γ(G) of G is defined as follows. The vertices of Γ(G) are the primes dividing the order of G and two distinct vertices p and p′ are joined by an edge if there is an element in G of order pp′. We denote by k(Γ(G)) the number of isomorphism classes of finite groups H satisfying Γ(G) = Γ(H). Given a natural number r, a finite group G is called r-recognizable by prime graph if k(Γ(G)) =  r. In Shen et al. (Sib. Math. J. 51(2):244–254, 2010), it is proved that if p is an odd prime, then B _p (3) is recognizable by element orders. In this paper as the main result, we show that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then \({G\cong B_p(3)}\) or C _p (3). Also if Γ(G) = Γ(B ₃(3)), then \({G\cong B_3(3), C_3(3), D_4(3)}\), or \({G/O_2(G)\cong {\rm Aut}(^2B_2(8))}\). As a corollary, the main result of the above paper is obtained.     

Critical Independent Sets and König–Egerváry Graphs

A set S of vertices is independent or stable in a graph G, and we write S ∈ Ind (G), if no two vertices from S are adjacent, and α(G) is the cardinality of an independent set of maximum size, while core(G) denotes the intersection of all maximum independent sets. G is called a König–Egerváry graph if its order equals α(G) + μ(G), where μ(G) denotes the size of a maximum matching. The number def (G) = | V(G) | ?2μ(G) is the deficiency of G. The number \({d(G)=\max\{\left\vert S\right\vert -\left\vert N(S)\right\vert :S\in\mathrm{Ind}(G)\}}\) is the critical difference of G. An independent set A is critical if \({\left\vert A\right\vert -\left\vert N(A)\right\vert =d(G)}\) , where N(S) is the neighborhood of S, and α _c (G) denotes the maximum size of a critical independent set. Larson (Eur J Comb 32:294–300, 2011) demonstrated that G is a König–Egerváry graph if and only if there exists a maximum independent set that is also critical, i.e., α _c (G) = α(G). In this paper we prove that: (i) \({d(G)=\left \vert \mathrm{core}(G) \right \vert -\left \vert N (\mathrm{core}(G))\right\vert =\alpha(G)-\mu(G)=def \left(G\right)}\) holds for every König–Egerváry graph G; (ii) G is König–Egerváry graph if and only if each maximum independent set of G is critical.     

Graphs of nonsolvable groups with four degree-vertices

Let G be a finite group. The degree(vertex) graph Γ(G) attached to G is a character degree graph.Its vertices are the degrees of the nonlinear irreducible complex characters of G, and different vertices m, n are adjacent if the greatest common divisor(m, n) 1. In this paper, we classify all graphs with four vertices that occur as Γ(G) for nonsolvable groups G.     

Every graph is (2,3)-choosable

A total weighting of a graph G is a mapping ? that assigns to each element z ∈ V (G)∪E(G) a weight ?(z). A total weighting ? is proper if for any two adjacent vertices u and v, ∑ _e∈E(u) ?(e)+?(u)≠∑ _e∈E(v) ?(e)+?(v). This paper proves that if each edge e is given a set L(e) of 3 permissible weights, and each vertex v is given a set L(v) of 2 permissible weights, then G has a proper total weighting ? with ?(z) ∈ L(z) for each element z ∈ V (G)∪E(G).     

On the diameter of the intersection graph of a finite simple group

Let G be a finite group. The intersection graph Δ_G of G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper nontrivial subgroups of G, and two distinct vertices X and Y are adjacent if X ∩ Y ≠ 1, where 1 denotes the trivial subgroup of order 1. A question was posed by Shen (2010) whether the diameters of intersection graphs of finite non-abelian simple groups have an upper bound. We answer the question and show that the diameters of intersection graphs of finite non-abelian simple groups have an upper bound 28. In particular, the intersection graph of a finite non-abelian simple group is connected.     

On weakly <Emphasis Type="Italic">S</Emphasis>Φ-supplemented subgroups of finite groups

Let G be a finite group. We say that a subgroup H of G is weakly SΦ-supplemented in G if G has a subgroup T such that G = HT and H∩T ≤ Φ(H)H_sG, where H_sG is the subgroup of H generated by all those subgroups of H that are s-permutable in G. In this paper, we investigate the influence of weakly SΦ-supplemented subgroups on the structure of finite groups. Some new characterizations of p-nilpotency and supersolubility of finite groups are obtained.     

<Emphasis Type="Italic">r</Emphasis>-Dynamic Chromatic Number of Some Line Graphs

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that |c(N(v))| ≥ min {r, deg(v)}, for each v ∈ V (G). The r-dynamic chromatic number of a graph G is the smallest k such that G admits an r-dynamic coloring with k colors. In this paper, we obtain the r-dynamic chromatic number of the line graph of helm graphs H_n for all r between minimum and maximum degree of H_n. Moreover, our proofs are constructive, what means that we give also polynomial time algorithms for the appropriate coloring. Finally, as the first, we define an equivalent model for edge coloring.     

Spectra of Automorphic Extensions of Finite Simple Exceptional Groups of Lie Type

The spectrum ω (G) of a finite group G is the set of orders of elements of G. Let S be a simple exceptional group of type E ₆ or E ₇ . We describe all finite groups G such that S ≤ G ≤ Aut S and ω (G) = ω (S) and completes the study of the recognition-by-spectrum problem for all simple exceptional groups of Lie type.     

Unicyclic nonintegral sum graphs

A graph G = (V,E) is an integral sum graph if there exists a labeling S(G) ? Z such that V = S(G) and every two distinct vertices u, υ ∈ V are adjacent if and only if u + υ ∈ V. A connected graph G = (V,E) is called unicyclic if |V| = |E|. In this paper two infinite series are constructed of unicyclic graphs that are not integral sum graphs.     

Extremely primitive groups and linear spaces

A non-regular primitive permutation group is called extremely primitive if a point stabilizer acts primitively on each of its nontrivial orbits. Let S be a nontrivial finite regular linear space and G ≤ Aut(S). Suppose that G is extremely primitive on points and let rank(G) be the rank of G on points. We prove that rank(G) ≥ 4 with few exceptions. Moreover, we show that Soc(G) is neither a sporadic group nor an alternating group, and G = PSL(2, q) with q + 1 a Fermat prime if Soc(G) is a finite classical simple group.