Neighborhood Conditions for Fractional ID-<Emphasis Type="Italic">k</Emphasis>-factor-critical Graphs

Let G be a graph and k ≥ 2 a positive integer. Let h: E(G) → [0, 1] be a function. If \(\sum\limits_{e \mathrel\backepsilon x} {h(e) = k} \) holds for each x ∈ V (G), then we call G[F_h] a fractional k-factor of G with indicator function h where F_h = {e ∈ 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 n ≥ 9k ? 14 and for any subset X ? V (G) we have

$${N_G}(X) = V(G)if|X| \geqslant \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ;or|{N_G}(X)| \geqslant \frac{{3k - 1}}{k}|X|if|X| < \left\lfloor {\frac{{kn}}{{3k - 1}}} \right\rfloor ,$$

then G is fractional ID-k-factor-critical.

     

Graphs with small total rainbow connection number

A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc(G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that \({\text{trc(G) = 3 if}}\left( {\begin{array}{*{20}{c}}{n - 1} \\2\end{array}} \right) + 1 \leqslant \left| {{\text{E(G)}}} \right| \leqslant \left( {\begin{array}{*{20}{c}}n \\2\end{array}} \right) - 1\), and \({\text{trc(G)}} \leqslant {\text{6 if }}\left| {{\text{E(G)}}} \right| \geqslant \left( {\begin{array}{*{20}{c}}{n - 2} \\2\end{array}} \right) + 2\). Next, we investigate the total rainbow connection numbers of graphs G with |V(G)| = n, diam(G) ≥ 2, and clique number ω(G) = n ? s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31(2): 313–320] is not completely correct, and we provide a complete result for this theorem.     

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.     

On <Emphasis Type="Italic">k</Emphasis>- critical 2<Emphasis Type="Italic">k</Emphasis>- connected graphs

A graph G is called an (n,k)-graph if κ(G-S)=n-|S| for any S ? V(G) with |S| ≤ k, where ?(G) denotes the connectivity of G. Mader conjectured that for k ≥ 3 the graph K_2k+2?(1-factor) is the unique (2k, k)-graph. Kriesell has settled two special cases for k = 3,4. We prove the conjecture for the general case k ≥ 5.     

A note on a result of Skiba

A subgroup H of a group G is called weakly s-permutable in G if there is a subnormal subgroup T of G such that G = HT and H ∩ T ≤ H _sG , where H _sG is the maximal s-permutable subgroup of G contained in H. We improve a nice result of Skiba to get the following

Theorem. Let ? be a saturated formation containing the class of all supersoluble groups

Open image in new window

and let G be a group with E a normal subgroup of G such that G/E ∈ ?. Suppose that each noncyclic Sylow p-subgroup P of F*(E) has a subgroup D such that 1 < |D| < |P| and all subgroups H of P with order |H| = |D| are weakly s-permutable in G for all p ∈ π(F*(E)); moreover, we suppose that every cyclic subgroup of P of order 4 is weakly s-permutable in G if P is a nonabelian 2-group and |D| = 2. Then G ∈ ?.

     

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.     

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.     

Finite groups with some non-Abelian subgroups of non-prime-power order

Let G be a finite group and NA(G) denote the number of conjugacy classes of all nonabelian subgroups of non-prime-power order of G. The Symbol π(G) denote the set of the prime divisors of |G|. In this paper we establish lower bounds on NA(G). In fact, we show that if G is a finite solvable group, then NA(G) = 0 or NA(G) ≥ 2^|π(G)|?2, and if G is non-solvable, then NA(G) ≥ |π(G)| + 1. Both lower bounds are best possible.     

<Emphasis Type="Italic">s</Emphasis>-Vertex Pancyclic Index

A graph G is vertex pancyclic if for each vertex \({v \in V(G)}\) , and for each integer k with 3 ≤ k ≤ |V(G)|, G has a k-cycle C _k such that \({v \in V(C_k)}\) . Let s ≥ 0 be an integer. If the removal of at most s vertices in G results in a vertex pancyclic graph, we say G is an s-vertex pancyclic graph. Let G be a simple connected graph that is not a path, cycle or K _1,3. Let l(G) = max{m : G has a divalent path of length m that is not both of length 2 and in a K ₃}, where a divalent path in G is a path whose interval vertices have degree two in G. The s-vertex pancyclic index of G, written vp _s (G), is the least nonnegative integer m such that L ^m (G) is s-vertex pancyclic. We show that for a given integer s ≥ 0,

$vp_s(G)\le \left\{\begin{array}{l@{\quad}l}\qquad\quad\quad\,\,\,\,\,\,\, l(G)+s+1: \quad {\rm if} \,\, 0 \le s \le 4 \\ l(G)+\lceil {\rm log}_2(s-2) \rceil+4: \quad {\rm if} \,\, s \ge 5 \end{array}\right.$

And we improve the bound for essentially 3-edge-connected graphs. The lower bound and whether the upper bound is sharp are also discussed.

     

On an inverse problem to Frobenius’ theorem

Let G be a finite group and e a positive integer dividing |G|, the order of G. Denoting \({L_e(G)=\{x\in G|\,x^e=1\}}\) , Frobenius proved that |L _e (G)| = ke for a positive integer k ≥ 1. In this paper, we give a complete classification of finite groups G with |L _e (G)| ≤ 2e for every e dividing |G|.     

Restrained Domination in Claw-Free Graphs with Minimum Degree at Least Two

Let G = (V, E) be a graph. A set \({S\subseteq V}\) is a restrained dominating set if every vertex in V ? S is adjacent to a vertex in S and to a vertex in V ? S. The restrained domination number of G, denoted γ _r (G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is claw-free with minimum degree at least two and \({G\notin \{C_{4},C_{5},C_{7},C_{8},C_{11},C_{14},C_{17}\}}\) , then \({\gamma_{r}(G)\leq \frac{2n}{5}.}\)     

The prime-power hypothesis and solvable groups

We say that a group G satisfies the prime-power hypothesis if the GCDs for all pairs of distinct character degrees are prime powers. We prove that if G is a solvable group satisfying the prime-power hypothesis, then G has Fitting height at most 12. If in addition |G| is odd, then we prove that the Fitting height of G is at most 6.     

2-Recognizability by prime graph of <Emphasis Type="Italic">PSL</Emphasis>(2, <Emphasis Type="Italic">p</Emphasis><Superscript>2</Superscript>)

Let G be a finite group and let Γ(G) be the prime graph of G. Assume p prime. We determine the finite groups G such that Γ(G) = Γ(PSL(2, p ²)) and prove that if p ≠ 2, 3, 7 is a prime then k(Γ(PSL(2, p ²))) = 2. We infer that if G is a finite group satisfying |G| = |PSL(2, p ²)| and Γ(G) = Γ(PSL(2, p ²)) then G ? PSL(2, p ²). This enables us to give new proofs for some theorems; e.g., a conjecture of W. Shi and J. Bi. Some applications are also considered of this result to the problem of recognition of finite groups by element orders.     

Subgraph Transversal of Graphs

Given graphs F and G, denote by \({\tau_F}(G)\) the cardinality of a smallest subset \(T {\subseteq}V(G)\) that meets every maximal F-free subgraph of G. Erdös, Gallai and Tuza [9] considered the question of bounding \(\tau_{\overline{K_2}}(G)\) by a constant fraction of |G|. In this paper, we will give a complete answer to the following question: for which F, is τ _F (G) bounded by a constant fraction of |G|?In addition, for those graphs F for which \({\tau_F}(G)\) is not bounded by any fraction of |G|, we prove that \(\tau_F(G)\le|G|-\frac{1}{2}\sqrt{|G|}+\frac{1}{2}\), provided F is not K _k or \(\overline{K_k}\).     

On recognizability of some finite simple orthogonal groups by spectrum

It is proved that, if G is a finite group that has the same set of element orders as the simple group D _p (q), where p is prime, p ≥ 5 and q ∈ {2, 3, 5}, then the commutator group of G/F(G) is isomorphic to D _p (q), the subgroup F(G) is equal to 1 for q = 5 and to O _q (G) for q ∈ {2, 3}, F(G) ≤ G′, and |G/G′| ≤ 2.     

Finite groups with <Emphasis Type="Italic">C</Emphasis>-quasinormal subgroups

Consider some finite group G and a finite subgroup H of G. Say that H is c-quasinormal in G if G has a quasinormal subgroup T such that HT = G and T ∩ H is quasinormal in G. Given a noncyclic Sylow subgroup P of G, we fix some subgroup D such that 1 < |D| < | P| and study the structure of G under the assumption that all subgroups H of P of the same order as D, having no supersolvable supplement in G, are c-quasinormal in G.     

Outer-2-independent domination in graphs

We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)?D has a neighbor in D and the maximum vertex degree of the subgraph induced by V(G)?D is at most one. The outer-2-independent domination number of a graph G is the minimum cardinality of an outer-2-independent dominating set of G. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.     

Cycles in dense digraphs

Let G be a digraph (without parallel edges) such that every directed cycle has length at least four; let β(G) denote the size of the smallest subset X ? E(G) such that G?X has no directed cycles, and let γ(G) be the number of unordered pairs {u, v} of vertices such that u, v are nonadjacent in G. It is easy to see that if γ(G) = 0 then β(G) = 0; what can we say about β(G) if γ(G) is bounded?

We prove that in general β(G) ≤ γ(G). We conjecture that in fact β(G) ≤ ½γ(G) (this would be best possible if true), and prove this conjecture in two special cases:

• when V(G) is the union of two cliques
• when the vertices of G can be arranged in a circle such that if distinct u, v, w are in clockwise order and uw is a (directed) edge, then so are both uv, vw.

     

Positive-fraction intersection results and variations of weak epsilon-nets

A connected Finsler space (M, F) is said to be homogeneous if it admits a transitive connected Lie group G of isometries. A geodesic in a homogeneous Finsler space (G / H, F) is called a homogeneous geodesic if it is an orbit of a one-parameter subgroup of G. In this paper, we study the problem of the existence of homogeneous geodesics on a homogeneous Finsler space, and prove that any homogeneous Finsler space of odd dimension admits at least one homogeneous geodesic through each point.     

Large $${\varvec{p}}^{\prime }$$-orbits for $${\varvec{p}}$$p-nilpotent linear groups

Let G be a p-nilpotent linear group on a finite vector space V of characteristic p. Suppose that |G||V| is odd. Let P be a Sylow p-subgroup of G. We show that there exist vectors \(v_1\) and \(v_2\) in V such that \(C_G(v_1) \cap C_G(v_2)=P\). A striking conjecture of Malle and Navarro offers a simple global criterion for the nilpotence (in the sense of Broué and Puig) of a p-block of a finite group. Our result implies that this conjecture holds for groups of odd order.