On All Fractional （a,b, k）-Critical Graphs

Let a,b,k,r be nonnegative integers with 1≤a≤b and r≥2.LetG be a graph of order n with n(a+b)(r(a+b)-2)+ak/a.In this paper,we first show a characterization for all fractional(a,b,k)-critical graphs.Then using the result,we prove that G is all fractional(a,b,k)-critical if δ(G)≥(r-1)b2/a+k and |NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b for any independent subset {x1,x2,...,xr} in G.Furthermore,it is shown that the lower bound on the condition|NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b is best possible in some sense,and it is an extension of Lu's previous result.     

Note on Group Distance Magic Graphs G[C 4]

A group distance magic labeling or a ${\mathcal{G}}$ -distance magic labeling of a graph G =  (V, E) with ${|V | = n}$ is a bijection f from V to an Abelian group ${\mathcal{G}}$ of order n such that the weight ${w(x) = \sum_{y\in N_G(x)}f(y)}$ of every vertex ${x \in V}$ is equal to the same element ${\mu \in \mathcal{G}}$ , called the magic constant. In this paper we will show that if G is a graph of order n =  2 ^p (2k + 1) for some natural numbers p, k such that ${\deg(v)\equiv c \mod {2^{p+1}}}$ for some constant c for any ${v \in V(G)}$ , then there exists a ${\mathcal{G}}$ -distance magic labeling for any Abelian group ${\mathcal{G}}$ of order 4n for the composition G[C ₄]. Moreover we prove that if ${\mathcal{G}}$ is an arbitrary Abelian group of order 4n such that ${\mathcal{G} \cong \mathbb{Z}_2 \times\mathbb{Z}_2 \times \mathcal{A}}$ for some Abelian group ${\mathcal{A}}$ of order n, then there exists a ${\mathcal{G}}$ -distance magic labeling for any graph G[C ₄], where G is a graph of order n and n is an arbitrary natural number.     

Independence number and minimum degree for fractional ID-k-factor-critical graphs

Let k be an integer with k?≥?1, and let G be a graph. A k-factor of G is a spanning subgraph F of G such that d _F (x)?=?k for each ${x\in V(G)}$ . Let ${h:E(G)\rightarrow[0,1]}$ be a function. If ${\sum_{e\ni x}h(e)=k}$ holds for each ${x\in V(G)}$ , then we call G[F _h ] a fractional k-factor of G with indicator function h, where ${F_h=\{e\in E(G): h(e) >0 \}}$ . A graph G is fractional independent-set-deletable k-factor-critical (in short, fractional ID-k-factor-critical) if G?I has a fractional k-factor for every independent set I of G. In this paper, we prove that if ${\alpha(G)\leq\frac{4k(\delta(G)-k+1)}{k^{2}+6k+1}}$ , then G is fractional ID-k-factor-critical. The result is best possible in some sense.     

Binding number and Hamiltonian(g, f)-factors in graphs

A(g, f)-factorF of a graphG is called a Hamiltonian(g, f)-factor ifF contains a Hamiltonian cycle. The binding number ofG is defined by $bind(G) = \min \left\{ {\frac{{|N_G (X)|}}{{|X|}}|\not 0 \ne X \subset V(G), N_G (X) \ne V(G)} \right\}$ . Let G be a connected graph, and let a andb be integers such that 4 ≤ a <b. Letg, f be positive integer-valued functions defined onV(G) such that a ≤g(x) < f(x) ≤ b for everyx ∈V(G). In this paper, it is proved that if $bind(G) \geqslant \frac{{(a + b - 5)(n - 1)}}{{(a - 2)n - 3(a + b - 5)}}, \nu (G) \geqslant \frac{{(a + b - 5)^2 }}{{a - 2}}$ and for any nonempty independent subset X ofV(G), thenG has a Hamiltonian(g, f)-factor.     

Finite groups with some NR-subgroups or {\mathcal{H}}-subgroups

Berkovich investigated the following concept: a subgroup H of a finite group G is called an NR-subgroup (Normal Restriction) if whenever ${K \trianglelefteq H}$ , then ${K^G \cap H = K}$ , where K ^G is the normal closure of K in G. Bianchi, Gillio Berta Mauri, Herzog and Verardi proved a characterization of soluble T-groups by means of ${\mathcal{H}}$ -subgroups: a subgroup H of G is said to be an ${\mathcal{H}}$ -subgroup of G if ${H^g \cap N_G(H) \leq H}$ for all ${g \in G}$ . In this article we give new characterizations of finite soluble PST-groups in terms of NR-subgroups or ${\mathcal{H}}$ -subgroups. We will show that they are different from the ones given by Ballester-Bolinches, Esteban-Romero and Pedraza-Aguilera. Robinson established the structure of minimal non-PST-groups. We give the classification of groups all of whose second maximal subgroups (of even order) are soluble PST-groups.     

On Graphlike k-Dissimilarity Vectors

Let \({\mathcal{G} = (G, w)}\) be a positive-weighted simple finite connected graph, that is, let G be a simple finite connected graph endowed with a function w from the set of edges of G to the set of positive real numbers. For any subgraph \({G^\prime}\) of G, we define \({w(G^\prime)}\) to be the sum of the weights of the edges of \({G^\prime}\) . For any i ₁, . . . , i _k vertices of G, let \({D_{\{i_1,..., i_k\}} (\mathcal{G})}\) be the minimum of the weights of the subgraphs of G connecting i ₁, . . . , i _k . The \({D_{\{i_1,..., i_k\}}(\mathcal{G})}\) are called k-weights of \({\mathcal{G}}\) . Given a family of positive real numbers parametrized by the k-subsets of {1, . . . , n}, \({{\{D_I\}_{I} \in { \{1,...,n\} \choose k}}}\) , we can wonder when there exist a weighted graph \({\mathcal{G}}\) (or a weighted tree) and an n-subset {1, . . . , n} of the set of its vertices such that \({D_I (\mathcal{G}) = D_I}\) for any \({I} \in { \{1,...,n\} \choose k}\) . In this paper we study this problem in the case k =  n?1.     

Upper bounds on the signed (k, k)-domatic number

Let G be a graph with vertex set V(G), and let f : V(G) → {?1, 1} be a two-valued function. If k ≥ 1 is an integer and ${\sum_{x\in N[v]} f(x) \ge k}$ for each ${v \in V(G)}$ , where N[v] is the closed neighborhood of v, then f is a signed k-dominating function on G. A set {f ₁,f ₂, . . . ,f _d } of distinct signed k-dominating functions on G with the property that ${\sum_{i=1}^d f_i(x) \le k}$ for each ${x \in V(G)}$ , is called a signed (k, k)-dominating family (of functions) on G. The maximum number of functions in a signed (k, k)-dominating family on G is the signed (k, k)-domatic number of G. In this article we mainly present upper bounds on the signed (k, k)-domatic number, in particular for regular graphs.     

Closure and Spanning k-Trees

In this paper, we propose a new closure concept for spanning k-trees. A k-tree is a tree with maximum degree at most k. We prove that: Let G be a connected graph and let u and v be nonadjacent vertices of G. Suppose that \({\sum_{w \in S}d_G(w) \geq |V(G)| -1}\) for every independent set S in G of order k with \({u,v \in S}\) . Then G has a spanning k-tree if and only if G + uv has a spanning k-tree. This result implies Win’s result (Abh Math Sem Univ Hamburg, 43:263–267, 1975) and Kano and Kishimoto’s result (Graph Comb, 2013) as corollaries.     

Minimum degree of bipartite graphs and the existence ofk-factors

LetG be a bipartite graph with bipartition (X, Y) andk a positive integer. If (i) $$\left| X \right| = \left| Y \right|,$$ (ii) $$\delta (G) \geqslant \left\lceil {\frac{{\left| X \right|}}{2}} \right\rceil \geqslant k,$$ \(\left| X \right| \geqslant 4k - 4\sqrt k + 1\) when |X| is odd and |X| ≥ 4k ? 2 when |X| is even, thenG has ak-factor.     

Splitter Theorems for 4-Regular Graphs

Let ${\Phi_{k,g}}$ be the class of all k-edge connected 4-regular graphs with girth of at least g. For several choices of k and g, we determine a set ${\mathcal{O}_{k,g}}$ of graph operations, for which, if G and H are graphs in ${\Phi_{k,g}}$ , G ≠ H, and G contains H as an immersion, then some operation in ${\mathcal{O}_{k,g}}$ can be applied to G to result in a smaller graph G′ in ${\Phi_{k,g}}$ such that, on one hand, G′ is immersed in G, and on the other hand, G′ contains H as an immersion.     

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.     

2-Reducible Two Paths and an Edge Constructing a Path in (2k + 1)-Edge-Connected Graphs

Let k ≥ 5 be an odd integer and G = (V(G), E(G)) be a k-edge-connected graph. For ${X\subseteq V(G),e(X)}$ denotes the number of edges between X and V(G) ? X. We here prove that if ${\{s_i,t_i\}\subseteq X_i\subseteq V(G)(i=1,2),f}$ is an edge between s ₁ and ${s_2,X_1\cap X_2=\emptyset,e(X_1)\le 2k-3,e(X_2)\le 2k-2}$ , and e(Y) ≥ k + 1 for each ${Y\subseteq V(G)}$ with ${Y\cap\{s_1,t_1,s_2,t_2\}=\{s_1,t_2\}}$ , then there exist paths P ₁ and P ₂ such that P _i joins s _i and ${t_i,V(P_i)\subseteq X_i}$ (i = 1, 2) and ${G-f-E(P_1\cup P_2)}$ is (k ? 2)-edge-connected, and in fact we give a generalization of this result.     

Levi Factors of the Special Fiber of a Parahoric Group Scheme and Tame Ramification

Let $\cal{A}$ be a Henselian discrete valuation ring with fractions K and with perfect residue field k of characteristic p?>?0. Let G be a connected and reductive algebraic group over K, and let $\cal{P}$ be a parahoric group scheme over $\cal{A}$ with generic fiber ${\cal{P}}_{/K} = G$ . The special fiber ${\cal{P}}_{/k}$ is a linear algebraic group over k. If G splits over an unramified extension of K, we proved in some previous work that the special fiber ${\cal{P}}_{/k}$ has a Levi factor, and that any two Levi factors of ${\cal{P}}_{/k}$ are geometrically conjugate. In the present paper, we extend a portion of this result. Following a suggestion of Gopal Prasad, we prove that if G splits over a tamely ramified extension of K, then the geometric special fiber ${\cal{P}}_{/k_{\rm{alg}}}$ has a Levi factor, where k _alg is an algebraic closure of k.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

The crossing function of a graph

The crossing function of a graphG with orientable genusn is defined as a mapping \(f:\{ \not 0,1, \ldots ,n\} \to \{ \not 0,1,2, \ldots \} \) for whichf(k)=cr _k (G) the crossing number ofG on the orientable surface of genusk. It is proved that any decreasing convex function \(f:\{ \not 0,1, \ldots ,n\} \to \{ \not 0,1,2, \ldots \} \) with \(f(n) = \not 0\) is the crossing function of some connected graph.     

The t-Tone Chromatic Number of Random Graphs

A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from \({\binom{[k]}{2}}\) such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph G, denoted τ ₂(G) is the smallest k such that G admits a proper 2-tone k coloring. In this paper, we prove that w.h.p. for \({p\geq Cn^{-1/4} {\rm ln}^{9/4}n, \tau_2(G_{n, p}) = (2 + o(1))\chi(G_{n, p})}\) where \({\chi}\) represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that \({\tau_2(G_{n, p}) = \lceil{({\sqrt{8\Delta + 1} + 5})/{2}}}\) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.     

On the Lucky Choice Number of Graphs

Suppose that G is a graph and ${f: V (G) \rightarrow \mathbb{N}}$ is a labeling of the vertices of G. Let S(v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if ${S(u) \neq S(v),}$ for every pair of adjacent vertices u and v. Also, for each vertex ${v \in V(G),}$ let L(v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that ${f(v) \in L(v),}$ for each ${v \in V(G).}$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η _l (G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with ${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too.     

On Group Choosability of Graphs,II

Given a group A and a directed graph G, let F(G, A) denote the set of all maps ${f : E(G) \rightarrow A}$ . Fix an orientation of G and a list assignment ${L : V(G) \mapsto 2^A}$ . For an ${f \in F(G, A)}$ , G is (A, L, f)-colorable if there exists a map ${c:V(G) \mapsto \cup_{v \in V(G)}L(v)}$ such that ${c(v) \in L(v)}$ , ${\forall v \in V(G)}$ and ${c(x)-c(y)\neq f(xy)}$ for every edge e = xy directed from x to y. If for any ${f\in F(G,A)}$ , G has an (A, L, f)-coloring, then G is (A, L)-colorable. If G is (A, L)-colorable for any group A of order at least k and for any k-list assignment ${L:V(G) \rightarrow 2^A}$ , then G is k-group choosable. The group choice number, denoted by ${\chi_{gl}(G)}$ , is the minimum k such that G is k-group choosable. In this paper, we prove that every planar graph is 5-group choosable, and every planar graph with girth at least 5 is 3-group choosable. We also consider extensions of these results to graphs that do not have a K ₅ or a K _3,3 as a minor, and discuss group choosability versions of Hadwiger’s and Woodall’s conjectures.     

b-Chromatic Number of Cartesian Product of Some Families of Graphs

A b-coloring of a graph G with k colors is a proper coloring of G using k colors in which each color class contains a color dominating vertex, that is, a vertex which has a neighbor in each of the other color classes. The largest positive integer k for which G has a b-coloring using k colors is the b-chromatic number b(G) of G. It is known that for any two graphs G and H, ${b(G \square H) \geq {\rm {max}} \{b(G), b(H)\}}$ , where ${\square}$ stands for the Cartesian product. In this paper, we determine some families of graphs G and H for which strict inequality holds. More precisely, we show that for these graphs G and H, ${b(G \square H) \geq b(G) + b(H) - 1}$ . This generalizes one of the results due to Kouider and Mahéo.     

Additive Coloring of Planar Graphs

An additive coloring of a graph G is an assignment of positive integers \({\{1,2,\ldots ,k\}}\) to the vertices of G such that for every two adjacent vertices the sums of numbers assigned to their neighbors are different. The minimum number k for which there exists an additive coloring of G is denoted by \({\eta (G)}\) . We prove that \({\eta (G) \, \leqslant \, 468}\) for every planar graph G. This improves a previous bound \({\eta (G) \, \leqslant \, 5544}\) due to Norin. The proof uses Combinatorial Nullstellensatz and the coloring number of planar hypergraphs. We also demonstrate that \({\eta (G) \, \leqslant \, 36}\) for 3-colorable planar graphs, and \({\eta (G) \, \leqslant \, 4}\) for every planar graph of girth at least 13. In a group theoretic version of the problem we show that for each \({r \, \geqslant \, 2}\) there is an r-chromatic graph G _r with no additive coloring by elements of any abelian group of order r.