Packing chromatic number versus chromatic and clique number

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in [k]\), where each \(V_i\) is an i-packing. In this paper, we investigate for a given triple (a, b, c) of positive integers whether there exists a graph G such that \(\omega (G) = a\), \(\chi (G) = b\), and \(\chi _{\rho }(G) = c\). If so, we say that (a, b, c) is realizable. It is proved that \(b=c\ge 3\) implies \(a=b\), and that triples \((2,k,k+1)\) and \((2,k,k+2)\) are not realizable as soon as \(k\ge 4\). Some of the obtained results are deduced from the bounds proved on the packing chromatic number of the Mycielskian. Moreover, a formula for the independence number of the Mycielskian is given. A lower bound on \(\chi _{\rho }(G)\) in terms of \(\Delta (G)\) and \(\alpha (G)\) is also proved.     

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

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.     

Packing Chromatic Number of Base-3 Sierpiński Graphs

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that there exists a k-vertex coloring of G in which any two vertices receiving color i are at distance at least \(i+1\). Let \(S^n\) be the base-3 Sierpiński graph of dimension n. It is proved that \(\chi _{\rho }(S^1) = 3\), \(\chi _{\rho }(S^2) = 5\), \(\chi _{\rho }(S^3) = \chi _{\rho }(S^4) = 7\), and that \(8\le \chi _\rho (S^n) \le 9\) holds for any \(n\ge 5\).     

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

On the density of images of the power maps in Lie groups

Let G be a connected Lie group. In this paper, we study the density of the images of individual power maps \(P_k:G\rightarrow G:g\mapsto g^k\). We give criteria for the density of \(P_k(G)\) in terms of regular elements, as well as Cartan subgroups. In fact, we prove that if \(\mathrm{Reg}(G)\) is the set of regular elements of G, then \(P_k(G)\cap \mathrm{Reg}(G)\) is closed in \(\mathrm{Reg}(G)\). On the other hand, the weak exponentiality of G turns out to be equivalent to the density of all the power maps \(P_k\). In linear Lie groups, weak exponentiality reduces to the density of \(P_2(G)\). We also prove that the density of the image of \(P_k\) for G implies the same for any connected full rank subgroup.     

On color-preserving automorphisms of Cayley graphs of odd square-free order

An automorphism \(\alpha \) of a Cayley graph \(\mathrm{Cay}(G,S)\) of a group G with connection set S is color-preserving if \(\alpha (g,gs) = (h,hs)\) or \((h,hs^{-1})\) for every edge \((g,gs)\in E(\mathrm{Cay}(G,S))\). If every color-preserving automorphism of \(\mathrm{Cay}(G,S)\) is also affine, then \(\mathrm{Cay}(G,S)\) is a Cayley color automorphism (CCA) graph. If every Cayley graph \(\mathrm{Cay}(G,S)\) is a CCA graph, then G is a CCA group. Hujdurovi? et al. have shown that every non-CCA group G contains a section isomorphic to the non-abelian group \(F_{21}\) of order 21. We first show that there is a unique non-CCA Cayley graph \(\Gamma \) of \(F_{21}\). We then show that if \(\mathrm{Cay}(G,S)\) is a non-CCA graph of a group G of odd square-free order, then \(G = H\times F_{21}\) for some CCA group H, and \(\mathrm{Cay}(G,S) = \mathrm{Cay}(H,T)\mathbin {\square }\Gamma \).     

On the Real Roots of $$\sigma $$-Polynomials

The \(\sigma \)-polynomial is given by \(\sigma (G,x) = \sum _{i=\chi (G)}^{n} a_{i}(G)\, x^{i}\), where \(a_{i}(G)\) is the number of partitions of the vertices of G into i nonempty independent sets. These polynomials are closely related to chromatic polynomials, as the chromatic polynomial of G is given by \(\sum _{i=\chi (G)}^{n} a_{i}(G)\, x(x-1) \ldots (x-(i-1))\). It is known that the closure of the real roots of chromatic polynomials is precisely \(\{0,~1\} \bigcup [32/27,\infty )\), with \((-\infty ,0)\), (0, 1) and (1, 32 / 27) being maximal zero-free intervals for roots of chromatic polynomials. We ask here whether such maximal zero-free intervals exist for \(\sigma \)-polynomials, and show that the only such interval is \([0,\infty )\)—that is, the closure of the real roots of \(\sigma \)-polynomials is \((-\infty ,0]\).     

Carter subgroups and Fitting heights of finite groups

Let G be a finite group possessing a Carter subgroup K. Denote by \(\mathbf {h}(G)\) the Fitting height of G, by \(\mathbf {h}^*(G)\) the generalized Fitting height of G, and by \(\ell (K)\) the number of composition factors of K, that is, the number of prime divisors of the order of K with multiplicities. In 1969, E. C. Dade proved that if G is solvable, then \(\mathbf {h}(G)\) is bounded in terms of \(\ell (K)\). In this paper, we show that \(\mathbf {h}^*(G)\) is bounded in terms of \(\ell (K)\) as well.     

Upper Bounds for the Paired-Domination Numbers of Graphs

A set \(S\subseteq V\) is a paired-dominating set if every vertex in \(V{\setminus } S\) has at least one neighbor in S and the subgraph induced by S contains a perfect matching. The paired-domination number of a graph G, denoted by \(\gamma _{pr}(G)\), is the minimum cardinality of a paired-dominating set of G. A conjecture of Goddard and Henning says that if G is not the Petersen graph and is a connected graph of order n with minimum degree \(\delta (G)\ge 3\), then \(\gamma _{pr}(G)\le 4n/7\). In this paper, we confirm this conjecture for k-regular graphs with \(k\ge 4\).     

Depth,Stanley depth,and regularity of ideals associated to graphs

Let \({\mathbb{K}}\) be a field and \({S=\mathbb{K}[x_1,\dots,x_n]}\) be the polynomial ring in n variables over \({\mathbb{K}}\). Let G be a graph with n vertices. Assume that \({I=I(G)}\) is the edge ideal of G and \({J=J(G)}\) is its cover ideal. We prove that \({{\rm sdepth}(J)\geq n-\nu_{o}(G)}\) and \({{\rm sdepth}(S/J)\geq n-\nu_{o}(G)-1}\), where \({\nu_{o}(G)}\) is the ordered matching number of G. We also prove the inequalities \({{\rmsdepth}(J^k)\geq {\rm depth}(J^k)}\) and \({{\rm sdepth}(S/J^k)\geq {\rmdepth}(S/J^k)}\), for every integer \({k\gg 0}\), when G is a bipartite graph. Moreover, we provide an elementary proof for the known inequality reg\({(S/I)\leq \nu_{o}(G)}\).     

2-Domination number of generalized Petersen graphs

Let \(G=(V,E)\) be a graph. A subset \(S\subseteq V\) is a k-dominating set of G if each vertex in \(V-S\) is adjacent to at least k vertices in S. The k-domination number of G is the cardinality of the smallest k-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs \(P(5k+1, 2)\) and \(P(5k+2, 2)\), for \(k>0\), is \(4k+2\) and \(4k+3\), respectively. This proves two conjectures due to Cheng (Ph.D. thesis, National Chiao Tung University, 2013). Moreover, we determine the exact 2-domination number of generalized Petersen graphs P(2k, k) and \(P(5k+4,3)\). Furthermore, we give a good lower and upper bounds on the 2-domination number of generalized Petersen graphs \(P(5k+1, 3), P(5k+2,3)\) and \(P(5k+3, 3).\)     

Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

Induced Cycles in Graphs

The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by \(c_\mathrm{ind}(G)\). We prove that if G is an r-regular graph of order n, then \(c_\mathrm{ind}(G) \ge \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}\) and we prove that if G is a cubic, claw-free graph on order n, then \(c_\mathrm{ind}(G) > \frac{13}{20}n\) and this bound is asymptotically best possible.     

Closed range and nonclosed range adjointable operators on Hilbert $$C^*$$-modules

In this paper, we show that for a positive operator A on a Hilbert \(C^*\)-module \( \mathscr {E} \), the range \( \mathscr {R}(A) \) of A is closed if and only if \( \mathscr {R}(A^\alpha ) \) is closed for all \(\alpha \in (0,1)\cup (1,+\,\infty )\), and this occurs if and only if \( \mathscr {R}(A)=\mathscr {R}(A^\alpha ) \) for all \(\alpha \in (0,1)\cup (1,+\,\infty )\). As an application, we prove that for an adjontable operator A if \(\mathscr {R}(A)\) is nonclosed, then \(\dim \left( \overline{\mathscr {R}(A)}/\mathscr {R}(A)\right) =+\,\infty \). Finally, we show that for an adjointable operator A if \( \overline{\mathscr {R}(A^*) } \) is orthogonally complemented in \( \mathscr {E} \), then under certain coditions there exists an idempotent C and a unique operator X such that \( XAX=X, AXA=CA, AX=C \) and \( XA=P_{A^*} \), where \( P_{A^*} \) is the orthogonal projection of \( \mathscr {E} \) onto \( \overline{\mathscr {R}(A^*)}\).     

Heinz mean curvature estimates in warped product spaces $$M\times _{e^{\psi }}N$$

If a graph submanifold (x, f(x)) of a Riemannian warped product space \((M^m\times _{e^{\psi }}N^n,\tilde{g}=g+ e^{2\psi }h)\) is immersed with parallel mean curvature H, then we obtain a Heinz-type estimation of the mean curvature. Namely, on each compact domain D of M, \(m\Vert H\Vert \le \frac{A_{\psi }(\partial D)}{V_{\psi }(D)}\) holds, where \(A_{\psi }(\partial D)\) and \(V_{\psi }(D)\) are the \({\psi }\)-weighted area and volume, respectively. In particular, \(H=0\) if (M, g) has zero-weighted Cheeger constant, a concept recently introduced by Impera et al. (Height estimates for killing graphs. arXiv:1612.01257, 2016). This generalizes the known cases \(n=1\) or \(\psi =0\). We also conclude minimality using a closed calibration, assuming \((M,g_*)\) is complete where \(g_*=g+e^{2\psi }f^*h\), and for some constants \(\alpha \ge \delta \ge 0\), \(C_1>0\) and \(\beta \in [0,1)\), \(\Vert \nabla ^*\psi \Vert ^2_{g_*}\le \delta \), \(\mathrm {Ricci}_{\psi ,g_*}\ge \alpha \), and \({\mathrm{det}}_g(g_*)\le C_1 r^{2\beta }\) holds when \(r\rightarrow +\infty \), where r(x) is the distance function on \((M,g_*)\) from some fixed point. Both results rely on expressing the squared norm of the mean curvature as a weighted divergence of a suitable vector field.     

A geometric approach to alternating <Emphasis Type="Italic">k</Emphasis>-linear forms

Denote by \({{\mathcal {G}}}_k(V)\) the Grassmannian of the k-subspaces of a vector space V over a field \({\mathbb {K}}\). There is a natural correspondence between hyperplanes H of \({\mathcal {G}}_k(V)\) and alternating k-linear forms on V defined up to a scalar multiple. Given a hyperplane H of \({{\mathcal {G}}_k}(V)\), we define a subspace \(R^{\uparrow }(H)\) of \({{\mathcal {G}}_{k-1}}(V)\) whose elements are the \((k-1)\)-subspaces A such that all k-spaces containing A belong to H. When \(n-k\) is even, \(R^{\uparrow }(H)\) might be empty; when \(n-k\) is odd, each element of \({\mathcal {G}}_{k-2}(V)\) is contained in at least one element of \(R^{\uparrow }(H)\). In the present paper, we investigate several properties of \(R^{\uparrow }(H)\), settle some open problems and propose a conjecture.     

Blow-up solutions for Hardy–Sobolev equations on compact Riemannian manifolds

Let (M, g) be a smooth compact Riemannian manifold of dimension \(n\ge 6\), \(\xi _0\in M\), and we are concerned with the following Hardy–Sobolev elliptic equations:

$$\begin{aligned} -\Delta _gu+h(x)u=\frac{u^{2^{*}(s)-1-\epsilon }}{d_{g}(x,\xi _0)^s},\ \ \ \ u>0\ \ \mathrm{in} \ \ M, \end{aligned}$$

(0.1)

where \(\Delta _g\,=\,\mathrm{div}_g(\nabla )\) is the Laplace–Beltrami operator on M, h(x) is a \(C^1\) function on M, \(\epsilon \) is a sufficiently small real parameter, \(2^{*}(s):=\frac{2(n-s)}{n-2}\) is the critical Hardy–Sobolev exponent with \(s\in (0,2)\), and \(d_{g}\) is the Riemannian distance on M. Performing the Lyapunov–Schmidt reduction procedure, we obtain the existence of blow-up families of positive solutions of problem (0.1).

     

Metacyclic groups as automorphism groups of compact Riemann surfaces

Let X be a compact Riemann surface of genus \(g\ge 2\), and let G be a subgroup of \(\mathrm{Aut}(X)\). We show that if the Sylow 2-subgroups of G are cyclic, then \(|G|\le 30(g-1)\). If all Sylow subgroups of G are cyclic, then, with two exceptions, \(|G|\le 10(g-1)\). More generally, if G is metacyclic, then, with one exception, \(|G|\le 12(g-1)\). Each of these bounds is attained for infinitely many values of g.     

Disposition p-groups

For any prime p and positive integers c, d there is up to isomorphism a unique p-group \({G_{d}^{c}(p)}\) of least order having any (finite) p-group G with rank \({d(G) \le d}\) and Frattini class \({c_{p}(G) \le c}\) as epimorphic image. Here \({c_{p}(G) = n}\) is the least positive integer such that G has a central series of length n with all factors being elementary. This “disposition” p-group \({G_{d}^{c}(p)}\) has been examined quite intensively in the literature, sometimes controversially. The objective of this paper is to present a summary of the known facts, and to add some new results. For instance we show that for \({G = G_{d}^{c}(p)}\) the centralizer \({C_{G}(x) = \langle Z(G), x \rangle}\) whenever \({x \in G}\) is outside the Frattini subgroup, and that for odd p and \({d \ge 2}\) the group \({E = G_{d}^{c+1}(p)/(G_{d}^{c+1}(p))^{p^{c}}}\) is a distinguished Schur cover of G with \({E/Z(E) \cong G}\). We also have a fibre product construction of \({G_{d}^{c+1}(p)}\) in terms of \({G = G_{d}^{c}(p)}\) which might be of interest for Galois theory.