A 4/3-approximation for TSP on cubic 3-edge-connected graphs

For a 3-edge-connected cubic graph $G=(V,E)$, we give an algorithm to construct a connected Eulerian subgraph of $2G$ using at most $?4\left|V\right|∕3?$ edges.     

Cubic non-normal Cayley graphs of order 4p2

A Cayley graph $\mathrm{Cay}(G,S)$ on a group $G$ is said to be normal if the right regular representation $R\left(G\right)$ of $G$ is normal in the full automorphism group of $\mathrm{Cay}(G,S)$. In this paper all connected cubic non-normal Cayley graphs of order $4p^2$ are constructed explicitly for each odd prime $p$. It is shown that there are three infinite families of cubic non-normal Cayley graphs of order $4p^2$ with $p$ odd prime. Note that a complete classification of cubic non-Cayley vertex-transitive graphs of order $4p^2$ was given in [K. Kutnar, D. Marus?ic?, C. Zhang, On cubic non-Cayley vertex-transitive graphs, J. Graph Theory 69 (2012) 77–95]. As a result, a classification of cubic vertex-transitive graphs of order $4p^2$ can be deduced.     

Connectivity keeping stars or double-stars in 2-connected graphs

In Mader (2010), Mader conjectured that for every positive integer $k$ and every finite tree $T$ with order $m$, every $k$-connected, finite graph $G$ with $\delta \left(G\right)\ge ?\frac{3}{2}k?+m?1$ contains a subtree $T^{\prime }$ isomorphic to $T$ such that $G?V\left(T^{\prime }\right)$ is $k$-connected. In the same paper, Mader proved that the conjecture is true when $T$ is a path. Diwan and Tholiya (2009) verified the conjecture when $k=1$. In this paper, we will prove that Mader’s conjecture is true when $T$ is a star or double-star and $k=2$.     

Improved FPT algorithms for weighted independent set in bull-free graphs

Very recently, Thomassé et al. (2017) have given an FPT algorithm for Weighted Independent Set in bull-free graphs parameterized by the weight of the solution, running in time $2^{O\left(k^5\right)}?n^9$. In this article we improve this running time to $2^{O\left(k^2\right)}?n^7$. As a byproduct, we also improve the previous Turing-kernel for this problem from $O\left(k^5\right)$ to $O\left(k^2\right)$. Furthermore, for the subclass of bull-free graphs without holes of length at most $2p?1$ for $p\ge 3$, we speed up the running time to $2^{O(k?k^{\frac{1}{p?1}})}?n^7$. As $p$ grows, this running time is asymptotically tight in terms of $k$, since we prove that for each integer $p\ge 3$, Weighted Independent Set cannot be solved in time $2^{o\left(k\right)}?n^{O\left(1\right)}$ in the class of $\{\text{bull},C_4,\dots ,C_{2p?1}\}$-free graphs unless the ETH fails.     

The list L(2,1)-labeling of planar graphs

Let $\mathbf{N}$ be the set of all positive integers. A list assignment of a graph $G$ is a function $L:V\left(G\right)?2^{\mathbf{N}}$ that assigns each vertex $v$ a list $L\left(v\right)$ for all $v\in V\left(G\right)$. We say that $G$ is $L$-$(2,1)$-choosable if there exists a function $?$ such that $?\left(v\right)\in L\left(v\right)$ for all $v\in V\left(G\right)$, $|?\left(u\right)??\left(v\right)|\ge 2$ if $u$ and $v$ are adjacent, and $|?\left(u\right)??\left(v\right)|\ge 1$ if $u$ and $v$ are at distance 2. The list-$L(2,1)$-labeling number ${\lambda }_l\left(G\right)$ of $G$ is the minimum $k$ such that for every list assignment $L=\{L\left(v\right):|L\left(v\right)|=k,v\in V\left(G\right)\}$, $G$ is $L$-$(2,1)$-choosable. We prove that if $G$ is a planar graph with girth $g\ge 8$ and its maximum degree $\Delta$ is large enough, then ${\lambda }_l\left(G\right)\le \Delta +3$. There are graphs with large enough $\Delta$ and $g\ge 8$ having ${\lambda }_l\left(G\right)=\Delta +3$.     

Regular Hadamard matrices constructed from Hadamard 2-designs and conference graphs

Suppose there exists a Hadamard 2-$(m,\frac{m?1}{2},\frac{m?3}{4})$ design having skew incidence matrix. If there exists a conference graph on $2m?1$ vertices, then there exists a regular Hadamard matrix of order $4m^2$. A conference graph on $2m+3$ vertices yields a regular Hadamard matrix of order $4{(m+1)}^2$.     

On the spanning connectivity of the generalized Petersen graphs P(n,3)

In this paper, we employed lattice model to describe the three internally vertex-disjoint paths that span the vertex set of the generalized Petersen graph $P(n,3)$. We showed that the $P(n,3)$ is 3-spanning connected for odd $n$. Based on the lattice model, five amalgamated and one extension mechanisms are introduced to recursively establish the 3-spanning connectivity of the $P(n,3)$. In each amalgamated mechanism, a particular lattice trail was amalgamated with the lattice trails that was dismembered, transferred, or extended from parts of the lattice trails for $P(n?6,3)$, where a lattice tail is a trail in the lattice model that represents a path in $P(n,3)$.     

Convergence rates and interior estimates in homogenization of higher order elliptic systems

This paper is concerned with the quantitative homogenization of 2m-order elliptic systems with bounded measurable, rapidly oscillating periodic coefficients. We establish the sharp $O(\epsilon )$ convergence rate in $W^{m?1,p_0}$ with $p_0=\frac{2d}{d?1}$ in a bounded Lipschitz domain in ${\mathbb{R}}^d$ as well as the uniform large-scale interior $C^{m?1,1}$ estimate. With additional smoothness assumptions, the uniform interior $C^{m?1,1}$, $W^{m,p}$ and $C^{m?1,\alpha }$ estimates are also obtained. As applications of the regularity estimates, we establish asymptotic expansions for fundamental solutions.     

A new formula for the decycling number of regular graphs

The decycling number $?\left(G\right)$ of a graph $G$ is the smallest number of vertices which can be removed from $G$ so that the resultant graph contains no cycle. A decycling set containing exactly $?\left(G\right)$ vertices of $G$ is called a $?$-set. For any decycling set $S$ of a $k$-regular graph $G$, we show that $\left|S\right|=\frac{\beta \left(G\right)+m\left(S\right)}{k?1}$, where $\beta \left(G\right)$ is the cycle rank of $G$, $m\left(S\right)=c+\left|E\left(S\right)\right|?1$ is the margin number of $S$, $c$ and $\left|E\left(S\right)\right|$ are, respectively, the number of components of $G?S$ and the number of edges in $G\left[S\right]$. In particular, for any $?$-set $S$ of a 3-regular graph $G$, we prove that $m\left(S\right)=\xi \left(G\right)$, where $\xi \left(G\right)$ is the Betti deficiency of $G$. This implies that the decycling number of a 3-regular graph $G$ is $\frac{\beta \left(G\right)+\xi \left(G\right)}{2}$. Hence $?\left(G\right)=?\frac{\beta \left(G\right)}{2}?$ for a 3-regular upper-embeddable graph $G$, which concludes the results in [Gao et al., 2015, Wei and Li, 2013] and solves two open problems posed by Bau and Beineke (2002). Considering an algorithm by Furst et al., (1988), there exists a polynomial time algorithm to compute $Z\left(G\right)$, the cardinality of a maximum nonseparating independent set in a $3$-regular graph $G$, which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph $G$, we show that for any $?$-set $S$ of $G$, there exists a spanning tree $T$ of $G$ such that the elements of $S$ are simply the leaves of $T$ with at most two exceptions providing $?\left(G\right)=?\frac{\beta \left(G\right)}{3}?$. On the other hand, if $G$ is a loopless graph on $n$ vertices with maximum degree at most $4$, then

The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006).     

Independent domination in subcubic graphs of girth at least six

A set $S$ of vertices in a graph $G$ is an independent dominating set of $G$ if $S$ is an independent set and every vertex not in $S$ is adjacent to a vertex in $S$. The independent domination number, $i\left(G\right)$, of $G$ is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if $G$ is a bipartite, cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$. We show that the bipartite condition can be relaxed, and prove that if $G$ is a cubic graph of order $n$ and of girth at least $6$, then $i\left(G\right)\le \frac{4}{11}n$.     

Distinguishing chromatic number of random Cayley graphs

The distinguishing chromatic number of a graph $G$, denoted ${\chi }_D\left(G\right)$, is defined as the minimum number of colors needed to properly color $G$ such that no non-trivial automorphism of $G$ fixes each color class of $G$. In this paper, we consider random Cayley graphs $\Gamma$ defined over certain abelian groups $A$ with $\left|A\right|=n$, and show that with probability at least $1?n^{?\Omega (logn)}$, ${\chi }_D\left(\Gamma \right)\le \chi \left(\Gamma \right)+1$.     

Helly EPT graphs on bounded degree trees: Characterization and recognition

The edge-intersection graph of a family of paths on a host tree is called an $EPT$ graph. When the tree has maximum degree $h$, we say that the graph is $[h,2,2]$. If, in addition, the family of paths satisfies the Helly property, then the graph is Helly $[h,2,2]$. In this paper, we present a family of $EPT$ graphs called gates which are forbidden induced subgraphs for $[h,2,2]$ graphs. Using these we characterize by forbidden induced subgraphs the Helly $[h,2,2]$ graphs. As a byproduct we prove that in getting a Helly $EPT$-representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly $[h,2,2]$ graphs based on their decomposition by maximal clique separators.     

On the number of rainbow spanning trees in edge-colored complete graphs

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m?1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $?\sqrt{6m+9}∕3?$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.     

On constructing normal and non-normal Cayley graphs

Bamberg and Giudici (2011) showed that the point graphs of certain generalised quadrangles of order $(q?1,q+1)$, where $q=p^k$ is a prime power with $p\ge 5$, are both normal and non-normal Cayley graphs for two isomorphic groups. We call these graphs BG-graphs. In this paper, we show that the Cayley graphs obtained from a finite number of BG-graphs by Cartesian product, direct product, and strong product also possess the property of being normal and non-normal Cayley graphs for two isomorphic groups.