Coloring of the Square of Kneser Graph $$$$

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n elements set, with two vertices adjacent if they are disjoint. The square \(G^2\) of a graph G is the graph defined on V(G) such that two vertices u and v are adjacent in \(G^2\) if the distance between u and v in G is at most 2. Determining the chromatic number of the square of the Kneser graph K(n, k) is an interesting graph coloring problem, and is also related with intersecting family problem. The square of K(2k, k) is a perfect matching and the square of K(n, k) is the complete graph when \(n \ge 3k-1\). Hence coloring of the square of \(K(2k +1, k)\) has been studied as the first nontrivial case. In this paper, we focus on the question of determining \(\chi (K^2(2k+r,k))\) for \(r \ge 2\). Recently, Kim and Park (Discrete Math 315:69–74, 2014) showed that \(\chi (K^2(2k+1,k)) \le 2k+2\) if \( 2k +1 = 2^t -1\) for some positive integer t. In this paper, we generalize the result by showing that for any integer r with \(1 \le r \le k -2\),

1. (a)
   \(\chi (K^2 (2k+r, k)) \le (2k+r)^r\),   if   \(2k + r = 2^t\) for some integer t, and
    
2. (b)
   \(\chi (K^2 (2k+r, k)) \le (2k+r+1)^r\),   if  \(2k + r = 2^t-1\) for some integer t.
    

On the other hand, it was shown in Kim and Park (Discrete Math 315:69–74, 2014) that \(\chi (K^2 (2k+r, k)) \le (r+2)(3k + \frac{3r+3}{2})^r\) for \(2 \le r \le k-2\). We improve these bounds by showing that for any integer r with \(2 \le r \le k -2\), we have \(\chi (K^2 (2k+r, k)) \le 2 \left( \frac{9}{4}k + \frac{9(r+3)}{8} \right) ^r\). Our approach is also related with injective coloring and coloring of Johnson graph.

     

Relationships Between the 2-Metric Dimension and the 2-Adjacency Dimension in the Lexicographic Product of Graphs

Given a connected simple graph \(G=(V(G),E(G))\), a set \(S\subseteq V(G)\) is said to be a 2-metric generator for G if and only if for any pair of different vertices \(u,v\in V(G)\), there exist at least two vertices \(w_1,w_2\in S\) such that \(d_G(u,w_i)\ne d_G(v,w_i)\), for every \(i\in \{1,2\}\), where \(d_G(x,y)\) is the length of a shortest path between x and y. The minimum cardinality of a 2-metric generator is the 2-metric dimension of G, denoted by \(\dim _2(G)\). The metric \(d_{G,2}: V(G)\times V(G)\longmapsto {\mathbb {N}}\cup \{0\}\) is defined as \(d_{G,2}(x,y)=\min \{d_G(x,y),2\}\). Now, a set \(S\subseteq V(G)\) is a 2-adjacency generator for G, if for every two vertices \(x,y\in V(G)\) there exist at least two vertices \(w_1,w_2\in S\), such that \(d_{G,2}(x,w_i)\ne d_{G,2}(y,w_i)\) for every \(i\in \{1,2\}\). The minimum cardinality of a 2-adjacency generator is the 2-adjacency dimension of G, denoted by \({\mathrm {adim}}_2(G)\). In this article, we obtain closed formulae for the 2-metric dimension of the lexicographic product \(G\circ H\) of two graphs G and H. Specifically, we show that \(\dim _2(G\circ H)=n\cdot {\mathrm {adim}}_2(H)+f(G,H),\) where \(f(G,H)\ge 0\), and determine all the possible values of f(G, H).     

Locating Pairs of Vertices on a Hamiltonian Cycle in Bigraphs

Let G be a simple \(m\times m\) bipartite graph with minimum degree \(\delta (G)\ge m/2+1\). We prove that for every pair of vertices x, y, there is a Hamiltonian cycle in G such that the distance between x and y along that cycle equals k, where \(2\le k<m/6\) is an integer having appropriate parity. We conjecture that this is also true up to \(k\le m\).     

Optimal channel assignment and <Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">p</Emphasis>, 1)-labeling

The optimal channel assignment is an important optimization problem with applications in optical networks. This problem was formulated to the L(p, 1)-labeling of graphs by Griggs and Yeh (SIAM J Discrete Math 5:586–595, 1992). A k-L(p, 1)-labeling of a graph G is a function \(f:V(G)\rightarrow \{0,1,2,\ldots ,k\}\) such that \(|f(u)-f(v)|\ge p\) if \(d(u,v)=1\) and \(|f(u)-f(v)|\ge 1\) if \(d(u,v)=2\), where d(u, v) is the distance between the two vertices u and v in the graph. Denote \(\lambda _{p,1}^l(G)= \min \{k \mid G\) has a list k-L(p, 1)-labeling\(\}\). In this paper we show upper bounds \(\lambda _{1,1}^l(G)\le \Delta +9\) and \(\lambda _{2,1}^l(G)\le \max \{\Delta +15,29\}\) for planar graphs G without 4- and 6-cycles, where \(\Delta \) is the maximum vertex degree of G. Our proofs are constructive, which can be turned to a labeling (channel assignment) method to reach the upper bounds.     

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.     

Some infinite families of Ramsey ($${\varvec{P}}_\mathbf{3},{\varvec{P}}_{{\varvec{n}}}$$)-minimal trees

For any given two graphs G and H, the notation \(F\rightarrow \) (G, H) means that for any red–blue coloring of all the edges of F will create either a red subgraph isomorphic to G or a blue subgraph isomorphic to H. A graph F is a Ramsey (G, H)-minimal graph if \(F\rightarrow \) (G, H) but \(F-e\nrightarrow (G,H)\), for every \(e \in E(F)\). The class of all Ramsey (G, H)-minimal graphs is denoted by \(\mathcal {R}(G,H)\). In this paper, we construct some infinite families of trees belonging to \(\mathcal {R}(P_3,P_n)\), for \(n=8\) and 9. In particular, we give an algorithm to obtain an infinite family of trees belonging to \(\mathcal {R}(P_3,P_n)\), for \(n\ge 10\).     

Generic irreducibilty of Laplace eigenspaces on certain compact Lie groups

If G is a compact Lie group endowed with a left invariant metric g, then G acts via pullback by isometries on each eigenspace of the associated Laplace operator \(\Delta _g\). We establish algebraic criteria for the existence of left invariant metrics g on G such that each eigenspace of \(\Delta _g\), regarded as the real vector space of the corresponding real eigenfunctions, is irreducible under the action of G. We prove that generic left invariant metrics on the Lie groups \(G={ SU}(2)\times \cdots \times { SU}(2)\times T\), where T is a (possibly trivial) torus, have the property just described. The same holds for quotients of such groups G by discrete central subgroups. In particular, it also holds for \({ SO}(3)\), \({ U}(2)\), \({ SO}(4)\).     

Generalizations of Marriage Theorem for Degree Factors

Let G be a bipartite graph with bipartition (A, B). We give new criteria for a bipartite graph to have an f -factor, a (g, f)-factor and other factors together with some applications of these criteria. These criteria can be considered as direct generalizations of Hall’s marriage theorem. Among some results, we prove that for a function \(h: A\cup B \rightarrow \{0,1,2, \ldots \}\), G has a factor F such that \(\deg _F(x)=h(x)\) for \(x\in A\) and \(\deg _H(y) \le h(y)\) for \(y\in B\) if and only if \(h(X) \le \sum _{x\in N_G(X)}\min \{h(x), e_G(x,X)\}\) for all \(X\subseteq A\).     

Dispersion and Limit Theorems for Random Walks Associated with Hypergeometric Functions of Type <Emphasis Type="Italic">BC</Emphasis>

The spherical functions of the non-compact Grassmann manifolds \(G_{p,q}({\mathbb {F}})=G/K\) over the (skew-)fields \({\mathbb {F}}={\mathbb {R}}, {\mathbb {C}}, {\mathbb {H}}\) with rank \(q\ge 1\) and dimension parameter \(p>q\) can be described as Heckman–Opdam hypergeometric functions of type BC, where the double coset space G /  / K is identified with the Weyl chamber \( C_q^B\subset {\mathbb {R}}^q\) of type B. The corresponding product formulas and Harish-Chandra integral representations were recently written down by M. Rösler and the author in an explicit way such that both formulas can be extended analytically to all real parameters \(p\in [2q-1,\infty [\), and that associated commutative convolution structures \(*_p\) on \(C_q^B\) exist. In this paper, we study the associated moment functions and the dispersion of probability measures on \(C_q^B\) with the aid of this generalized integral representation. This leads to strong laws of large numbers and central limit theorems for associated time-homogeneous random walks on \((C_q^B, *_p)\) where the moment functions and the dispersion appear in order to determine drift vectors and covariance matrices of these limit laws explicitly. For integers p, all results have interpretations for G-invariant random walks on the Grassmannians G / K. Besides the BC-cases, we also study the spaces \(GL(q,{\mathbb {F}})/U(q,{\mathbb {F}})\), which are related to Weyl chambers of type A, and for which corresponding results hold. For the rank-one-case \(q=1\), the results of this paper are well known in the context of Jacobi-type hypergroups on \([0,\infty [\).     

On <Emphasis Type="Italic">G</Emphasis>-covering subgroup systems of finite groups

Let \(\mathcal{F}\) be a class of groups and G a finite group. We call a set Σ of subgroups of G a G-covering subgroup system for  \(\mathcal{F}\) if \(G\in \mathcal{F}\) whenever \(\Sigma \subseteq \mathcal{F}\). Let p be any prime dividing |G| and P a Sylow p-subgroup of G. Then we write Σ _p to denote the set of subgroups of G which contains at least one supplement to G of each maximal subgroup of P. We prove that the sets Σ _p and Σ _p ∪Σ _q , where q≠p, are G-covering subgroup systems for many classes of finite groups.     

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.     

Complexities of normal bases constructed from Gauss periods

Let q be a power of a prime p, and let \(r=nk+1\) be a prime such that \(r\not \mid q\), where n and k are positive integers. Under a simple condition on q, r and k, a Gauss period of type (n, k) is a normal element of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\); the complexity of the resulting normal basis of \({\mathbb {F}}_{q}^{n}\) over \({\mathbb {F}}_q\) is denoted by C(n, k; p). Recent works determined C(n, k; p) for \(k\le 7\) and all qualified n and q. In this paper, we show that for any given \(k>0\), C(n, k; p) is given by an explicit formula except for finitely many primes \(r=nk+1\) and the exceptional primes are easily determined. Moreover, we describe an algorithm that allows one to compute C(n, k; p) for the exceptional primes \(r=nk+1\). Our numerical results cover C(n, k; p) for \(k\le 20\) and all qualified n and q.     

Relative Difference Sets and Hadamard Matrices from Perfect Quaternionic Arrays

Let \(G=\mathbf{C}_{n_1}\times \cdots \times \mathbf{C}_{n_m}\) be an abelian group of order \(n=n_1\dots n_m\), where each \(\mathbf{C}_{n_t}\) is cyclic of order \(n_t\). We present a correspondence between the (4n, 2, 4n, 2n)-relative difference sets in \(G\times Q_8\) relative to the centre \(Z(Q_8)\) and the perfect arrays of size \(n_1\times \dots \times n_m\) over the quaternionic alphabet \(Q_8\cup qQ_8\), where \(q=(1+i+j+k)/2\). In view of this connection, for \(m=2\) we introduce new families of relative difference sets in \(G\times Q_8\), as well as new families of Williamson and Ito Hadamard matrices with G-invariant components.     

A group of continuous self-maps on a topological groupoid

The group of bisections of groupoids plays an important role in the study of Lie groupoids. In this paper another construction is introduced. Indeed, for a topological groupoid G, the set of all continuous self-maps f on G such that (x, f(x)) is a composable pair for every \(x\in G\), is denoted by \(S_G\). We show that \(S_G\) by a natural binary operation is a monoid. \(S_G(\alpha )\), the group of units in \(S_G\) precisely consists of those \(f\in S_G\) such that the map \(x\mapsto xf(x)\) is a bijection on G. Similar to the group of bisections, \(S_G(\alpha )\) acts on G from the right and on the space of continuous self-maps on G from the left. It is proved that \(S_G(\alpha )\) with the compact- open topology inherited from C(G, G) is a left topological group. For a compact Hausdorff groupoid G it is proved that the group of bisections of \(G^2\) is isomorphic to the group \(S_G(\alpha )\) and the group of transitive bisections of G, \(Bis_T(G)\), is embedded in \(S_G(\alpha )\), where \(G^2\) is the groupoid of all composable pairs.     

Sharpening an Ore-type version of the Corrádi–Hajnal theorem

Corrádi and Hajnal (Acta Math Acad Sci Hung 14:423–439, 1963) proved that for all \(k\ge 1\) and \(n\ge 3k\), every (simple) graph G on n vertices with minimum degree \(\delta (G)\ge 2k\) contains k disjoint cycles. The degree bound is sharp. Enomoto and Wang proved the following Ore-type refinement of the Corrádi–Hajnal theorem: For all \(k\ge 1\) and \(n\ge 3k\), every graph G on n vertices contains k disjoint cycles, provided that \(d(x)+d(y)\ge 4k-1\) for all distinct nonadjacent vertices x, y. Very recently, it was refined for \(k\ge 3\) and \(n\ge 3k+1\): If G is a graph on n vertices such that \(d(x)+d(y)\ge 4k-3\) for all distinct nonadjacent vertices x, y, then G has k vertex-disjoint cycles if and only if the independence number \(\alpha (G)\le n-2k\) and G is not one of two small exceptions in the case \(k=3\). But the most difficult case, \(n=3k\), was not handled. In this case, there are more exceptional graphs, the statement is more sophisticated, and some of the proofs do not work. In this paper we resolve this difficult case and obtain the full picture of extremal graphs for the Ore-type version of the Corrádi–Hajnal theorem. Since any k disjoint cycles in a 3k-vertex graph G must be 3-cycles, the existence of such k cycles is equivalent to the existence of an equitable k-coloring of the complement of G. Our proof uses the language of equitable colorings, and our result can be also considered as an Ore-type version of a partial case of the Chen–Lih–Wu Conjecture on equitable colorings.     

Most small $${\varvec{}}$$-grous have an automorhism of order 2

Let f(p, n) be the number of pairwise nonisomorphic p-groups of order \(p^n\), and let g(p, n) be the number of groups of order \(p^n\) whose automorphism group is a p-group. We prove that the limit, as p grows to infinity, of the ratio g(p, n) / f(p, n) equals 1/3 for \(n=6,7\).     

Fair 1-Factorizations and Fair Holey 1-Factorizations of Complete Multipartite Graphs

A k-factor of a graph G is a k-regular spanning subgraph of G. A k-factorization is a partition of E(G) into k-factors. Let K(n, p) be the complete multipartite graph with p parts, each of size n. If \(V_{1},\ldots , V_{p}\) are the p parts of V(K(n, p)), then a holey k -factor of deficiency \(V_{i}\) of K(n, p) is a k-factor of \(K(n,p)-V_{i}\) for some i satisfying \(1\le i \le p\). Hence a holey k -factorization is a set of holey k-factors whose edges partition E(K(n, p)). Representing each (holey) k-factor as a color class in an edge-coloring, a (holey) k-factorization of K(n, p) is said to be fair if between each pair of parts the color classes have size within one of each other (so the edges are shared “evenly” among the permitted (holey) factors). In this paper the existence of fair 1-factorizations of K(n, p) is completely settled, as is the existence of fair holey 1-factorizations of K(n, p). The latter result can be used to provide a new construction for symmetric quasigroups of order np with holes of size n. Such quasigroups have the additional property that the permitted symbols are shared as evenly as possible among the cells in each \(n \times n\) “box”. These quasigroups are in some sense as far from frames produced by direct products as possible.     

On a two-phase free boundary condition for <Emphasis Type="Italic">p</Emphasis>-harmonic measures

Let \({\Omega^i\subset {\bf R}^n, i\in\{1,2\}}\) , be two (δ, r ₀)-Reifenberg flat domains, for some \({0 < \delta < \hat \delta}\) and r ₀ > 0, assume \({\Omega^1\cap\Omega^2=\emptyset}\) and that, for some \({w\in {\bf R}^n}\) and some 0 < r, \({w\in\partial\Omega^1\cap\partial\Omega^2, \partial\Omega^1\cap B(w,2r)=\partial\Omega^2\cap B(w,2r)}\) . Let p, 1 < p < ∞, be given and let u ⁱ , \({i\in\{1,2\}}\) , denote a non-negative p-harmonic function in Ω ⁱ , assume that u ⁱ , \({i\in\{1,2\}}\), is continuous in \({\bar\Omega^i\cap B(w,2r) }\) and that u ⁱ  = 0 on \({\partial\Omega^i\cap B(w,2r)}\) . Extend u ⁱ to B(w, 2r) by defining \({u^i\equiv 0}\) on \({B(w,2r) {\setminus} \Omega^i}\). Then there exists a unique finite positive Borel measure μ ⁱ , \({i\in\{1,2\}}\) , on R ⁿ , with support in \({\partial\Omega^i\cap B(w,2r)}\) , such that if \({\phi \in C_0^\infty (B(w,2r))}\) , then

$\int\limits_{\mathbf R^n} \,|\nabla u^i|^{ p-2} \,\langle \nabla u^i, \,\nabla \phi \rangle \,dx =- \int\limits_{\mathbf R^n} \,\phi \,d \mu^i.$

Let \({\Delta(w,2r)=\partial\Omega^1\cap B(w,2r)=\partial\Omega^2\cap B(w,2r)}\) . The main result proved in this paper is the following. Assume that μ ² is absolutely continuous with respect to μ ¹ on Δ(w, 2r), d μ ² = kd μ ¹ for μ ¹-almost every point in Δ(w, 2r) and that \({\log k\in VMO(\Delta(w,r),\mu^1)}\) . Then there exists \({\tilde \delta = \tilde \delta(p,n) > 0}\) , \({\tilde \delta < \hat \delta}\) , such that if \({\delta\leq\tilde\delta}\) , then Δ(w, r/2) is Reifenberg flat with vanishing constant. Moreover, the special case p = 2, i.e., the linear case and the corresponding problem for harmonic measures, has previously been studied in Kenig and Toro (J Reine Angew Math 596:1–44, 2006).

     

A note on a result of Guo and Isaacs about p-supersolubility of finite groups

In this note, global information about a finite group is obtained by assuming that certain subgroups of some given order are S-semipermutable. Recall that a subgroup H of a finite group G is said to be S-semipermutable if H permutes with all Sylow subgroups of G of order coprime to \({\lvert H\rvert}\). We prove that for a fixed prime p, a given Sylow p-subgroup P of a finite group G, and a power d of p dividing \({\lvert G\rvert}\) such that \({1\le d < \lvert P\rvert}\), if \({H\,{\cap}\, O^p(G)}\) is S-semipermutable in \({O^p(G)}\) for all normal subgroups H of P with \({\lvert H\rvert=d}\), then either G is p-supersoluble or else \({\lvert P\,{\cap}\, {O^p(G)}\rvert > d}\). This extends the main result of Guo and Isaacs in (Arch. Math. 105:215–222 2015). We derive some theorems that extend some known results concerning S-semipermutable subgroups.     

Solution to a Problem on Hamiltonicity of Graphs Under Ore- and Fan-Type Heavy Subgraph Conditions

A graph G is called claw-o-heavy if every induced claw (\(K_{1,3}\)) of G has two end-vertices with degree sum at least |V(G)|. For a given graph S,  G is called S-f-heavy if for every induced subgraph H of G isomorphic to S and every pair of vertices \(u,v\in V(H)\) with \(d_H(u,v)=2,\) there holds \(\max \{d(u),d(v)\}\ge |V(G)|/2.\) In this paper, we prove that every 2-connected claw-o-heavy and \(Z_3\)-f-heavy graph is hamiltonian (with two exceptional graphs), where \(Z_3\) is the graph obtained by identifying one end-vertex of \(P_4\) (a path with 4 vertices) with one vertex of a triangle. This result gives a positive answer to a problem proposed Ning and Zhang (Discrete Math 313:1715–1725, 2013), and also implies two previous theorems of Faudree et al. and Chen et al., respectively.