Fractional f-Edge Cover Chromatic Index of Graphs

Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ _f (G) or δ _f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.     

The Signed k-Submatchings in Graphs

A signed k-submatching of a graph G is a function f : E(G) → {?1,1} satisfying f (E _G (v)) ≤ 1 for at least k vertices ${v \in V(G)}$ . The maximum of the values of f (E(G)), taken over all signed k-submatchings f, is called the signed k-submatching number and is denoted by ${\beta_S^{k}(G)}$ . In this paper, sharp bounds on ${\beta_S^{k}(G)}$ for general graphs are presented. Exact values of ${\beta_S^{k}(G)}$ for several classes of graphs are found.     

The Chvátal–Erdös Condition for Group Connectivity in Graphs

Let G be a graph and A an abelian group with the identity element 0 and ${|A| \geq 4}$ . Let D be an orientation of G. The boundary of a function ${f: E(G) \rightarrow A}$ is the function ${\partial f: V(G) \rightarrow A}$ given by ${\partial f(v) = \sum_{e \in E^+(v)}f(e) - \sum_{e \in E^-(v)}f(e)}$ , where ${v \in V(G), E^+(v)}$ is the set of edges with tail at v and ${E^-(v)}$ is the set of edges with head at v. A graph G is A-connected if for every b: V(G) → A with ${\sum_{v \in V(G)} b(v) = 0}$ , there is a function ${f: E(G) \mapsto A-\{0\}}$ such that ${\partial f = b}$ . A graph G is A-reduced to G′ if G′ can be obtained from G by contracting A-connected subgraphs until no such subgraph left. Denote by ${\kappa^{\prime}(G)}$ and α(G) the edge connectivity and the independent number of G, respectively. In this paper, we prove that for a 2-edge-connected simple graph G, if ${\kappa^{\prime}(G) \geq \alpha(G)-1}$ , then G is A-connected or G can be A-reduced to one of the five specified graphs or G is one of the 13 specified graphs.     

On the Broadcast Independence Number of Grid Graph

A broadcast on a nontrivial connected graph G is a function ${f:V \longrightarrow \{0, \ldots,\operatorname{diam}(G)\}}$ such that for every vertex ${v \in V(G)}$ , ${f(v) \leq e(v)}$ , where ${\operatorname{diam}(G)}$ denotes the diameter of G and e(v) denotes the eccentricity of vertex v. The broadcast independence number is the maximum value of ${\sum_{v \in V} f(v)}$ over all broadcasts f that satisfy ${d(u,v) > \max \{f(u), f(v)\}}$ for every pair of distinct vertices u, v with positive values. We determine this invariant for grid graphs ${G_{m,n} = P_m \square P_n}$ , where ${2 \leq m \leq n}$ and □ denotes the Cartesian product. We hereby answer one of the open problems raised by Dunbar et al. in (Discrete Appl Math 154:59–75, 2006).     

On the Picard principle for Δ?+?μ

Given a (local) Kato measure?μ on ${{\mathbb{R}^d} \setminus \{0\},\,d \ge 2}$ , let ${{\mathcal H}_0^{\Delta+\mu}(U)}$ be the convex cone of all continuous real solutions u?≥ 0 to the equation Δu?+?u μ?=?0 on the punctured unit ball U satisfying ${\lim_{|x|\to 1} u(x)=0}$ . It is shown that ${{\mathcal H}_0^{\Delta+\mu}(U)\ne \{0\}}$ if and only if the operator ${f\mapsto \int_U G(\cdot,y)f(y)\,d\mu(y)}$ , where G denotes the Green function on U, is bounded on ${\mathcal L^2(U,\mu)}$ and has a norm which is at most one. Moreover, extremal rays in ${{\mathcal H}_0^{\Delta+\mu}(U)}$ are characterized and it is proven that Δ?+?μ satisfies the Picard principle on U, that is, that ${{\mathcal H}_0^{\Delta+\mu}(U)}$ consists of one ray, provided there exists a suitable sequence of shells in U such that, on these shells,?μ is either small or not too far from being radial. Further, it is shown that the verification of the Picard principle can be localized. Several results on L ²-(sub)eigenfunctions and 3G-inequalities which are used in the paper, but may be of independent interest, are proved at the end of the paper.     

On Coprimality Graphs for Symmetric Groups

For G a group, X a subset of G and π a set of positive integers we define a graph ${\mathcal{C}_{\pi}(G,X)}$ whose vertex set is X with ${x,y \in X}$ joined by an edge provided x ≠ y and the order of xy is in π. Here we investigate ${\mathcal{C}_{\pi}(G,X)}$ when G is a finite symmetric group and X is a G-conjugacy class of elements of order p, p a prime.     

Circular Coloring of Planar Digraphs

Let D be a digraph. The circular chromatic number ${\chi_c(D)}$ and chromatic number ${\chi(D)}$ of D were proposed recently by Bokal et?al. Let ${\vec{\chi_c}(G)={\rm max}\{\chi_c(D)| D\, {\rm is\, an\, orientation\, of} G\}}$ . Let G be a planar graph and n?≥ 2. We prove that if the girth of G is at least ${\frac{10n-5}{3},}$ then ${\vec{\chi_c}(G)\leq \frac{n}{n-1}}$ . We also study the circular chromatic number of some special planar digraphs.     

The Edge Rotation Graph

Let P be a set of n points on the plane in general position, n ≥  3. The edge rotation graph ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ of P is the graph whose vertices are the plane geometric graphs on P with exactly k edges, two of which are adjacent if one can be obtained from the other by an edge rotation. In this paper we study some structural properties of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ , such as its connectivity and diameter. We show that if the vertices of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ are not triangulations of P, then it is connected and has diameter O(n ²). We also show that the chromatic number of ${\mathcal{E} \mathcal{R} \mathcal{G}(P,k)}$ is O(n), and show how to compute an implicit coloring of its vertices. We also study edge rotations in edge-labelled geometric graphs.     

On the Edge Connectivity of Direct Products with Dense Graphs

Let ${\kappa^{\prime}(G)}$ be the edge connectivity of G and G × H the direct product of G and H. Let H be any graph with minimal degree ${\delta(H)>|V(H)|/2}$ . We prove that for any graph ${G, \kappa^{\prime}(G\times H)=\textup{min}\{2\kappa^{\prime}(G)|E(H)|,\delta(G)\delta(H)\}}$ . In addition, the structure of minimum edge cuts is described. As an application, we present a necessary and sufficient condition for G × K _n (n ≥ 3) to be super edge connected.     

Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, i.e., can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let ${c_{\infty}(G)}$ denote the number of cops needed to capture the robber in a graph G in this variant. We characterize graphs G with c _??(G) =? 1, and give an ${O( \mid V(G)\mid^2)}$ algorithm for their detection. We prove a lower bound for c _?? of expander graphs, and use it to prove three things. The first is that if ${np \geq 4.2 {\rm log}n}$ then the random graph ${G= \mathcal{G}(n, p)}$ asymptotically almost surely has ${\eta_{1}/p \leq \eta_{2}{\rm log}(np)/p}$ , for suitable positive constants ${\eta_{1}}$ and ${\eta_{2}}$ . The second is that a fixed-degree random regular graph G with n vertices asymptotically almost surely has ${c_{\infty}(G) = \Theta(n)}$ . The third is that if G is a Cartesian product of m paths, then ${n/4km^2 \leq c_{\infty}(G) \leq n/k}$ , where ${n = \mid V(G)\mid}$ and k is the number of vertices of the longest path.     

Extinction profile of the logarithmic diffusion equation

Let ${N \geq 3}$ and u be the solution of u _t = Δ log u in ${\mathbb{R}^N \times (0, T)}$ with initial value u ₀ satisfying ${B_{k_1}(x, 0) \leq u_{0} \leq B_{k_2}(x, 0)}$ for some constants k ₁ > k ₂ > 0 where ${B_k(x, t) = 2(N - 2)(T - t)_{+}^{N/(N - 2)}/(k + (T - t)_{+}^{2/(N - 2)}|x|^{2})}$ is the Barenblatt solution for the equation and ${u_0 - B_{k_0} \in L^{1}(\mathbb{R}^{N})}$ for some constant k ₀ > 0 if ${N \geq 4}$ . We give a new different proof on the uniform convergence and ${L^1(\mathbb{R}^N)}$ convergence of the rescaled function ${\tilde{u}(x, s) = (T - t)^{-N/(N - 2)}u(x/(T - t)^{-1/(N - 2)}, t), s = -{\rm log}(T - t)}$ , on ${\mathbb{R}^N}$ to the rescaled Barenblatt solution ${\tilde{B}_{k_0}(x) = 2(N - 2)/(k_0 + |x|^{2})}$ for some k ₀ > 0 as ${s \rightarrow \infty}$ . When ${N \geq 4, 0 \leq u_0(x) \leq B_{k_0}(x, 0)}$ in ${\mathbb{R}^N}$ , and ${|u_0(x) - B_{k_0}(x, 0)| \leq f \in L^{1}(\mathbb{R}^{N})}$ for some constant k ₀ > 0 and some radially symmetric function f, we also prove uniform convergence and convergence in some weighted L ¹ space in ${\mathbb{R}^N}$ of the rescaled solution ${\tilde{u}(x, s)}$ to ${\tilde{B}_{k_0}(x)}$ as ${s \rightarrow \infty}$ .     

Duality of weighted anisotropic Besov and Triebel–Lizorkin spaces

Let A be an expansive dilation on ${{\mathbb R}^n}$ and w a Muckenhoupt ${\mathcal A_\infty(A)}$ weight. In this paper, for all parameters ${\alpha\in{\mathbb R} }$ and ${p,q\in(0,\infty)}$ , the authors identify the dual spaces of weighted anisotropic Besov spaces ${\dot B^\alpha_{p,q}(A;w)}$ and Triebel?CLizorkin spaces ${\dot F^\alpha_{p,q}(A;w)}$ with some new weighted Besov-type and Triebel?CLizorkin-type spaces. The corresponding results on anisotropic Besov spaces ${\dot B^\alpha_{p,q}(A; \mu)}$ and Triebel?CLizorkin spaces ${\dot F^\alpha_{p,q}(A; \mu)}$ associated with ${\rho_A}$ -doubling measure??? are also established. All results are new even for the classical weighted Besov and Triebel?CLizorkin spaces in the isotropic setting. In particular, the authors also obtain the ${\varphi}$ -transform characterization of the dual spaces of the classical weighted Hardy spaces on ${{\mathbb R}^n}$ .     

The Linear t-Colorings of Sierpiński-Like Graphs

A proper t-coloring of a graph G is a mapping ${\varphi: V(G) \rightarrow [1, t]}$ such that ${\varphi(u) \neq \varphi(v)}$ if u and v are adjacent vertices, where t is a positive integer. The chromatic number of a graph G, denoted by ${\chi(G)}$ , is the minimum number of colors required in any proper coloring of G. A linear t-coloring of a graph is a proper t-coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by ${lc(G)}$ , is the minimum t such that G has a linear t-coloring. In this paper, the linear t-colorings of Sierpiński-like graphs S(n, k), ${S^+(n, k)}$ and ${S^{++}(n, k)}$ are studied. It is obtained that ${lc(S(n, k))= \chi (S(n, k)) = k}$ for any positive integers n and k, ${lc(S^+(n, k)) = \chi(S^+(n, k)) = k}$ and ${lc(S^{++}(n, k)) = \chi(S^{++}(n, k)) = k}$ for any positive integers ${n \geq 2}$ and ${k \geq 3}$ . Furthermore, we have determined the number of paths and the length of each path in the subgraph induced by the union of any two color classes completely.     

On the number of conjugacy classes of π-elements in finite groups

Let G be a finite group and π be a set of primes. Put ${d_{\pi}(G) = k_{\pi}(G)/|G|_{\pi}}$ , where ${k_{\pi}(G)}$ is the number of conjugacy classes of π-elements in G and |G| _π is the π-part of the order of G. In this paper we initiate the study of this invariant by showing that if ${d_{\pi}(G) > 5/8}$ then G possesses an abelian Hall π-subgroup, all Hall π-subgroups of G are conjugate, and every π-subgroup of G lies in some Hall π-subgroup of G. Furthermore, we have ${d_{\pi}(G) = 1}$ or ${d_{\pi}(G) = 2/3}$ . This extends and generalizes a result of W. H. Gustafson.     

Decomposition of Geodesics in the Wasserstein Space and the Globalization Problem

We will prove a decomposition for Wasserstein geodesics in the following sense: let (X, d, m) be a non-branching metric measure space verifying ${\mathsf{CD}_{loc}(K,N)}$ or equivalently ${\mathsf{CD}^{*}(K,N)}$ . We prove that every geodesic ${\mu_{t}}$ in the L ²-Wasserstein space, with ${\mu_{t} \ll m}$ , is decomposable as the product of two densities, one corresponding to a geodesic with support of codimension one verifying ${\mathsf{CD}^{*}(K,N-1)}$ , and the other associated with a precise one dimensional measure, provided the length map enjoys local Lipschitz regularity. The motivation for our decomposition is in the use of the component evolving like ${\mathsf{CD}^{*}}$ in the globalization problem. For a particular class of optimal transportation we prove the linearity in time of the other component, obtaining therefore the global ${\mathsf{CD}(K,N)}$ for ${\mu_{t}}$ . The result can be therefore interpret as a globalization theorem for ${\mathsf{CD}(K,N)}$ for this class of optimal transportation, or as a “self-improving property” for ${\mathsf{CD}^{*}(K,N)}$ . Assuming more regularity, namely in the setting of infinitesimally strictly convex metric measure space, the one dimensional density is the product of two differentials giving more insight on the density decomposition.     

Proper holomorphic mappings, Bell’s formula, and the Lu Qi-Keng problem on the tetrablock

We consider proper holomorphic maps ${\pi : D\rightarrow G}$ , where D and G are domains in ${\mathbb{C}^{n}}$ . Let ${\alpha\in \mathcal{C}(G,\mathbb{R}_{ > 0})}$ . We show that every π induces some subspace H of ${\mathbb{A}^{2}_{\alpha\circ\pi}(D)}$ such that ${\mathbb{A}^{2}_{\alpha}(G)}$ is isometrically isomorphic to H via some unitary operator Γ. Using this isomorphism we construct the orthogonal projection onto H, and we derive Bell’s transformation formula for the weighted Bergman kernel function under proper holomorphic mappings. As a consequence of the formula, we get that the tetrablock is not a Lu Qi-Keng domain.     

Collapsible Graphs and Hamiltonicity of Line Graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53–69; Conjecture 8.6 of 1995) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D ₃(G) the set of vertices of degree 3 of graph G. For ${e = uv \in E(G)}$ , define d(e) = d(u) + d(v) ? 2 the edge degree of e, and ${\xi(G) = \min\{d(e) : e \in E(G)\}}$ . Denote by λ ^m (G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq7}$ is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq6}$ is collapsible; a 3-edge-connected graph with ${\xi(G)\geq6}$ , ${\lambda^2(G)\geq4}$ , and ${\lambda^3(G)\geq6}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq6}$ , and ${\lambda^3(G)\geq5}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with ${\xi(G)\geq5}$ , and ${\lambda^2(G)\geq4}$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L(G) with minimum degree at least 5 and ${|D_3(G)|\leq9}$ is Hamiltonian.     

On Zero-Sum {\mathbb{Z}_k} -Magic Labelings of 3-Regular Graphs

Let G =  (V, E) be a finite loopless graph and let (A, +) be an abelian group with identity 0. Then an A-magic labeling of G is a function ${\phi}$ from E into A ? {0} such that for some ${a \in A, \sum_{e \in E(v)} \phi(e) = a}$ for every ${v \in V}$ , where E(v) is the set of edges incident to v. If ${\phi}$ exists such that a =  0, then G is zero-sum A-magic. Let zim(G) denote the subset of ${\mathbb{N}}$ (the positive integers) such that ${1 \in zim(G)}$ if and only if G is zero-sum ${\mathbb{Z}}$ -magic and ${k \geq 2 \in zim(G)}$ if and only if G is zero-sum ${\mathbb{Z}_k}$ -magic. We establish that if G is 3-regular, then ${zim(G) = \mathbb{N} - \{2\}}$ or ${\mathbb{N} - \{2,4\}.}$      

The Roles Played by Order of Convexity or Starlikeness and the Bloch Condition in the Extension of Mappings from the Disk to the Ball

Let ${G: \mathbb {C}^{n-1} \rightarrow \mathbb {C}}$ be holomorphic such that G(0)?=?0 and DG(0)?=?0. When f is a convex (resp. starlike) normalized (f(0)?=?0, f??(0)?=?1) univalent mapping of the unit disk ${\mathbb {D}}$ in ${\mathbb {C}}$ , then the extension of f to the Euclidean unit ball ${\mathbb {B}}$ in ${\mathbb {C}^n}$ given by ${\Phi_G(f)(z)=(f(z_1)+G(\sqrt{f^{\prime}(z_1)} \, \hat{z}),\sqrt{f^{\prime}(z_1)}\, \hat{z})}$ , ${\hat{z}=(z_2,\dots,z_n) \in \mathbb {C}^{n-1}}$ , is known to be convex (resp. starlike) if G is a homogeneous polynomial of degree 2 with sufficiently small norm. Conversely, it is known that G cannot have terms of degree greater than 2 in its expansion about 0 in order for ${\Phi_G(f)}$ to be convex (resp. starlike), in general. We examine whether the restriction that f be either convex or starlike of a certain order ${\alpha \in (0,1]}$ allows, in general, for G to contain terms of degree greater than 2 and still have ${\Phi_G(f)}$ maintain the respective geometric property. Related extension results for convex and starlike Bloch mappings are also given.