[1, 2]-sets in graphs

A subset S⊆V$S\subseteq V$ in a graph G=(V,E)$G=(V,E)$ is a [j,k]$[j,k]$-set if, for every vertex v∈V?S$v\in V?S$, j≤|N(v)∩S|≤k$j\le |N\left(v\right)\cap S|\le k$ for non-negative integers j$j$ and k$k$, that is, every vertex v∈V?S$v\in V?S$ is adjacent to at least j$j$ but not more than k$k$ vertices in S$S$. In this paper, we focus on small j$j$ and k$k$, and relate the concept of [j,k]$[j,k]$-sets to a host of other concepts in domination theory, including perfect domination, efficient domination, nearly perfect sets, 2-packings, and k$k$-dependent sets. We also determine bounds on the cardinality of minimum [1, 2]-sets, and investigate extremal graphs achieving these bounds. This study has implications for restrained domination as well. Using a result for [1, 3]-sets, we show that, for any grid graph G$G$, the restrained domination number is equal to the domination number of G$G$.     

Bounds on the connected domination number of a graph

A subset S$S$ of vertices in a graph G=(V,E)$G=(V,E)$ is a connected dominating set of G$G$ if every vertex of V?S$V?S$ is adjacent to a vertex in S$S$ and the subgraph induced by S$S$ is connected. The minimum cardinality of a connected dominating set of G$G$ is the connected domination number _γc(G)${\gamma }_c\left(G\right)$. The girth g(G)$g\left(G\right)$ is the length of a shortest cycle in G$G$. We show that if G$G$ is a connected graph that contains at least one cycle, then _γc(G)≥g(G)−2${\gamma }_c\left(G\right)\ge g\left(G\right)-2$, and we characterize the graphs obtaining equality in this bound. We also establish various upper bounds on the connected domination number of a graph, as well as Nordhaus–Gaddum type results.     

The Laplacian polynomial and Kirchhoff index of graphs derived from regular graphs

Let R(G)$R\left(G\right)$ be the graph obtained from G$G$ by adding a new vertex corresponding to each edge of G$G$ and by joining each new vertex to the end vertices of the corresponding edge, and Q(G)$Q\left(G\right)$ be the graph obtained from G$G$ by inserting a new vertex into every edge of G$G$ and by joining by edges those pairs of these new vertices which lie on adjacent edges of G$G$. In this paper, we determine the Laplacian polynomials of R(G)$R\left(G\right)$ and Q(G)$Q\left(G\right)$ of a regular graph G$G$; on the other hand, we derive formulae and lower bounds of the Kirchhoff index of these graphs.     

On large semi-linked graphs

Let H$H$ be a multigraph, possibly with loops, and consider a set S⊆V(H)$S\subseteq V\left(H\right)$. A (simple) graph G$G$ is (H,S)$(H,S)$-semi-linked   if, for every injective map f:S→V(G)$f:S\to V\left(G\right)$, there exists an injective map g:V(H)?S→V(G)?f(S)$g:V\left(H\right)?S\to V\left(G\right)?f\left(S\right)$ and a set of |E(H)|$\left|E\left(H\right)\right|$ internally disjoint paths in G$G$ connecting pairs of vertices of  f(S)∪g(V(H)?S)$f\left(S\right)\cup g(V\left(H\right)?S)$ for every edge between the corresponding vertices of H$H$. This new concept of (H,S)$(H,S)$-semi-linkedness is a generalization of H$H$-linkedness  . We establish a sharp minimum degree condition for a sufficiently large graph G$G$ to be (H,S)$(H,S)$-semi-linked.     

Fixed point theorems for Reich type contractions on metric spaces with a graph

Let (X,d)$(X,d)$ be a metric space endowed with a graph G$G$ such that the set V(G)$V\left(G\right)$ of vertices of G$G$ coincides with X$X$. We define the notion of G$G$-Reich type maps and obtain a fixed point theorem for such mappings. This extends and subsumes many recent results which were obtained for other contractive type mappings on ordered metric spaces and for cyclic operators.     

On the complexity of the bondage and reinforcement problems

Let G=(V,E)$G=(V,E)$ be a graph. A subset D⊆V$D\subseteq V$ is a dominating set if every vertex not in D$D$ is adjacent to a vertex in D$D$. A dominating set D$D$ is called a total dominating set if every vertex in D$D$ is adjacent to a vertex in D$D$. The domination (resp. total domination) number of G$G$ is the smallest cardinality of a dominating (resp. total dominating) set of G$G$. The bondage (resp. total bondage) number of a nonempty graph G$G$ is the smallest number of edges whose removal from G$G$ results in a graph with larger domination (resp. total domination) number of G$G$. The reinforcement (resp. total reinforcement) number of G$G$ is the smallest number of edges whose addition to G$G$ results in a graph with smaller domination (resp. total domination) number. This paper shows that the decision problems for the bondage, total bondage, reinforcement and total reinforcement numbers are all NP-hard.     

Crossing number additivity over edge cuts

Consider a graph G$G$ with a minimal edge cut F$F$ and let _G1$G_1$, _G2$G_2$ be the two (augmented) components of G−F$G-F$. A long-open question asks under which conditions the crossing number of G$G$ is (greater than or) equal to the sum of the crossing numbers of _G1$G_1$ and _G2$G_2$—which would allow us to consider those graphs separately. It is known that crossing number is additive for |F|∈{0,1,2}$\left|F\right|\in \{0,1,2\}$ and that there exist graphs violating this property with |F|≥4$\left|F\right|\ge 4$. In this paper, we show that crossing number is additive for |F|=3$\left|F\right|=3$, thus closing the final gap in the question.     

Frobenius groups and retract rationality

Let k$k$ be any field, G$G$ be a finite group acting on the rational function field k(_xg:g∈G)$k(x_g:g\in G)$ by h⋅_xg=_xhg$h\cdot x_g=x_{hg}$ for any h,g∈G$h,g\in G$. Define k(G)=k(_xg:g∈G)^G$k\left(G\right)=k{(x_g:g\in G)}^G$. Noether’s problem asks whether k(G)$k\left(G\right)$ is rational (= purely transcendental) over k$k$. A weaker notion, retract rationality introduced by Saltman, is also very useful for the study of Noether’s problem. We prove that, if G$G$ is a Frobenius group with abelian Frobenius kernel, then k(G)$k\left(G\right)$ is retract k$k$-rational for any field k$k$ satisfying some mild conditions. As an application, we show that, for any algebraic number field k$k$, for any Frobenius group G$G$ with Frobenius complement isomorphic to S_L2(_F5)$S{L}_2\left({\mathbb{F}}_5\right)$, there is a Galois extension field K$K$ over k$k$ whose Galois group is isomorphic to G$G$, i.e. the inverse Galois problem is valid for the pair (G,k)$(G,k)$. The same result is true for any non-solvable Frobenius group if k(_ζ8)$k\left({\zeta }_8\right)$ is a cyclic extension of k$k$.     

A unified proof of Brooks’ theorem and Catlin’s theorem

Brooks’ theorem is a fundamental result in the theory of graph coloring. Catlin proved the following strengthening of Brooks’ theorem: Let d$d$ be an integer at least 3, and let G$G$ be a graph with maximum degree d$d$. If G$G$ does not contain _Kd+1$K_{d+1}$ as a subgraph, then G$G$ has a d$d$-coloring in which one color class has size α(G)$\alpha \left(G\right)$. Here α(G)$\alpha \left(G\right)$ denotes the independence number of G$G$. We give a unified proof of Brooks’ theorem and Catlin’s theorem.     

Applications of equivariant degree for gradient maps to symmetric Newtonian systems

We consider G=Γ×S¹$G=\Gamma \times S^1$ with Γ$\Gamma$ being a finite group, for which the complete Euler ring structure in U(G)$U\left(G\right)$ is described. The multiplication tables for Γ=_D6$\Gamma =D_6$, _S4$S_4$ and _A5$A_5$ are provided in the Appendix. The equivariant degree for G$G$-orthogonal maps is constructed using the primary equivariant degree with one free parameter. We show that the G$G$-orthogonal degree extends the degree for G$G$-gradient maps (in the case of G=Γ×S¹$G=\Gamma \times S^1$) introduced by G?ba in [K. G?ba, W. Krawcewicz, J. Wu, An equivariant degree with applications to symmetric bifurcation problems I: Construction of the degree, Bull. London. Math. Soc. 69 (1994) 377–398]. The computational results obtained are applied to a Γ$\Gamma$-symmetric autonomous Newtonian system for which we study the existence of 2π$2\pi$-periodic solutions. For some concrete cases, we present the symmetric classification of the solution set for the systems considered.     

Comment on “Kirchhoff index in line,subdivision and total graphs of a regular graph”

Let G$G$ be a connected regular graph. Denoted by t(G)$t\left(G\right)$ and Kf(G)$Kf\left(G\right)$ the total graph and Kirchhoff index of G$G$, respectively. This paper is to point out that Theorem 3.7 and Corollary 3.8 from “Kirchhoff index in line, subdivision and total graphs of a regular graph” [X. Gao, Y.F. Luo, W.W. Liu, Kirchhoff index in line, subdivision and total graphs of a regular graph, Discrete Appl. Math. 160(2012) 560–565] are incorrect, since the conclusion of a lemma is essentially wrong. Moreover, we first show the Laplacian characteristic polynomial of t(G)$t\left(G\right)$, where G$G$ is a regular graph. Consequently, by using Kf(G)$Kf\left(G\right)$, we give an expression on Kf(t(G))$Kf\left(t\left(G\right)\right)$ and a lower bound on Kf(t(G))$Kf\left(t\left(G\right)\right)$ of a regular graph G$G$, which correct Theorem 3.7 and Corollary 3.8 in Gao et al. (2012)  [2].     

On prime ideals and radicals of polynomial rings and graded rings

We extend some known results on radicals and prime ideals from polynomial rings and Laurent polynomial rings to Z$\mathbb{Z}$-graded rings, i.e, rings graded by the additive group of integers. The main of them concerns the Brown–McCoy radical G$G$ and the radical S$S$, which for a given ring A$A$ is defined as the intersection of prime ideals I$I$ of A$A$ such that A/I$A/I$ is a ring with a large center. The studies are related to some open problems on the radicals G$G$ and S$S$ of polynomial rings and situated in the context of Koethe’s problem.     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

Disjoint cycles with different length in 4-arc-dominated digraphs

A d$d$-arc-dominated digraph is a digraph D$D$ of minimum out-degree d$d$ such that for every arc (x,y)$(x,y)$ of D$D$, there exists a vertex u$u$ of D$D$ of out-degree d$d$ such that (u,x)$(u,x)$ and (u,y)$(u,y)$ are arcs of D$D$. Henning and Yeo [Vertex disjoint cycles of different length in digraphs, SIAM J. Discrete Math. 26 (2012) 687–694] conjectured that a digraph with minimum out-degree at least four contains two vertex-disjoint cycles of different length. In this paper, we verify this conjecture for 4-arc-dominated digraphs.     

Large deviations of infinite intersections of events in Gaussian processes

Consider events of the form {_Zs≥ζ(s),s∈S}$\{Z_s\ge \zeta \left(s\right),s\in S\}$, where Z$Z$ is a continuous Gaussian process with stationary increments, ζ$\zeta$ is a function that belongs to the reproducing kernel Hilbert space R$R$ of process Z$Z$, and S⊂R$S\subset \mathbb{R}$ is compact. The main problem considered in this paper is identifying the function β^∗∈R${\beta }^{\ast }\in R$ satisfying β^∗(s)≥ζ(s)${\beta }^{\ast }\left(s\right)\ge \zeta \left(s\right)$ on S$S$ and having minimal R$R$-norm. The smoothness (mean square differentiability) of Z$Z$ turns out to have a crucial impact on the structure of the solution. As examples, we obtain the explicit solutions when ζ(s)=s$\zeta \left(s\right)=s$ for s∈[0,1]$s\in [0,1]$ and Z$Z$ is either a fractional Brownian motion or an integrated Ornstein–Uhlenbeck process.