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.     

[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$.     

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

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.     

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

Resolving sets for Johnson and Kneser graphs

A set of vertices S$S$ in a graph G$G$ is a resolving set   for G$G$ if, for any two vertices u,v$u,v$, there exists x∈S$x\in S$ such that the distances d(u,x)≠d(v,x)$d(u,x)\ne d(v,x)$. In this paper, we consider the Johnson graphs J(n,k)$J(n,k)$ and Kneser graphs K(n,k)$K(n,k)$, and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids.     

A new upper bound on the acyclic chromatic indices of planar graphs

An acyclic edge coloring of a graph G$G$ is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a^′(G)$a^{\prime }\left(G\right)$ of G$G$ is the smallest integer k$k$ such that G$G$ has an acyclic edge coloring using k$k$ colors. It was conjectured that a^′(G)≤Δ+2$a^{\prime }\left(G\right)\le \Delta +2$ for any simple graph G$G$ with maximum degree Δ$\Delta$. In this paper, we prove that if G$G$ is a planar graph, then a^′(G)≤Δ+7$a^{\prime }\left(G\right)\le \Delta +7$. This improves a result by Basavaraju et al. [M. Basavaraju, L.S. Chandran, N. Cohen, F. Havet, T. Müller, Acyclic edge-coloring of planar graphs, SIAM J. Discrete Math. 25 (2011) 463–478], which says that every planar graph G$G$ satisfies a^′(G)≤Δ+12$a^{\prime }\left(G\right)\le \Delta +12$.     

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.     

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

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.     

Minimum size transversals in uniform hypergraphs

A set of vertices in a hypergraph which meets all the edges is called a transversal. The transversal number τ(H)$\tau \left(H\right)$ of a hypergraph H$H$ is the minimum cardinality of a transversal in H$H$. A classical greedy algorithm for constructing a transversal of small size selects in each step a vertex which has the largest degree in the hypergraph formed by the edges not met yet. The analysis of this algorithm (by Chvátal and McDiarmid (1992)  [3]) gave some upper bounds for τ(H)$\tau \left(H\right)$ in a uniform hypergraph H$H$ with a given number of vertices and edges. We discuss a variation of this greedy algorithm. Analyzing this new algorithm, we obtain upper bounds for τ(H)$\tau \left(H\right)$ which improve the bounds by Chvátal and McDiarmid.