On 3-stable number conditions in n-connected claw-free graphs

For a subgraph $X$ of $G$, let ${\alpha }_G^3\left(X\right)$ be the maximum number of vertices of $X$ that are pairwise distance at least three in $G$. In this paper, we prove three theorems. Let $n$ be a positive integer, and let $H$ be a subgraph of an $n$-connected claw-free graph $G$. We prove that if $n\ge 2$, then either $H$ can be covered by a cycle in $G$, or there exists a cycle $C$ in $G$ such that ${\alpha }_G^3(H?V\left(C\right))\le {\alpha }_G^3\left(H\right)?n$. This result generalizes the result of Broersma and Lu that $G$ has a cycle covering all the vertices of $H$ if ${\alpha }_G^3\left(H\right)\le n$. We also prove that if $n\ge 1$, then either $H$ can be covered by a path in $G$, or there exists a path $P$ in $G$ such that ${\alpha }_G^3(H?V\left(P\right))\le {\alpha }_G^3\left(H\right)?n?1$. By using the second result, we prove the third result. For a tree $T$, a vertex of $T$ with degree one is called a leaf of $T$. For an integer $k\ge 2$, a tree which has at most $k$ leaves is called a $k$-ended tree. We prove that if ${\alpha }_G^3\left(H\right)\le n+k?1$, then $G$ has a $k$-ended tree covering all the vertices of $H$. This result gives a positive answer to the conjecture proposed by Kano et al. (2012).     

Rainbow number of matchings in planar graphs

The rainbow number$rb(G,H)$ for the graph $H$ in $G$ is defined to be the minimum integer $c$ such that any $c$-edge-coloring of $G$ contains a rainbow $H$. As one of the most important structures in graphs, the rainbow number of matchings has drawn much attention and has been extensively studied. Jendrol et al. initiated the rainbow number of matchings in planar graphs and they obtained bounds for the rainbow number of the matching $k{K}_2$ in the plane triangulations, where the gap between the lower and upper bounds is $O\left(k^3\right)$. In this paper, we show that the rainbow number of the matching $k{K}_2$ in maximal outerplanar graphs of order $n$ is $n+O\left(k\right)$. Using this technique, we show that the rainbow number of the matching $k{K}_2$ in some subfamilies of plane triangulations of order $n$ is $2n+O\left(k\right)$. The gaps between our lower and upper bounds are only $O\left(k\right)$.     

Characterization of the induced matching extendable graphs with 2n vertices and 3n edges

A graph $G$ is induced matching extendable or IM-extendable if every induced matching of $G$ is contained in a perfect matching of $G$. In 1998, Yuan proved that a connected IM-extendable graph on $2n$ vertices has at least $3n?2$ edges, and that the only IM-extendable graph with $2n$ vertices and $3n?2$ edges is $T\times K_2$ , where $T$ is an arbitrary tree on $n$ vertices. In 2005, Zhou and Yuan proved that the only IM-extendable graph with $2n\ge 6$ vertices and $3n?1$ edges is $T\times K_2+e$, where $T$ is an arbitrary tree on $n$ vertices and $e$ is an edge connecting two vertices that lie in different copies of $T$ and have distance 3 between them in $T\times K_2$. In this paper, we introduced the definition of $Q$-joint graph and characterized the connected IM-extendable graphs with $2n\ge 4$ vertices and $3n$ edges.     

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

A lower bound on the acyclic matching number of subcubic graphs

The acyclic matching number of a graph $G$ is the largest size of an acyclic matching in $G$, that is, a matching $M$ in $G$ such that the subgraph of $G$ induced by the vertices incident to edges in $M$ is a forest. We show that the acyclic matching number of a connected subcubic graph $G$ with $m$ edges is at least $m∕6$ except for two graphs of order 5 and 6.     

The weighted 2-metric dimension of trees in the non-landmarks model

Let $T=(V,E)$ be a tree graph with non-negative costs defined on the vertices. A vertex $\tau$ is called a separating vertex for $u$ and $v$ if the distances of $\tau$ to $u$ and $v$ are not equal. A set of vertices $L\subseteq V$ is a feasible solution for the non-landmarks model (NL), if for every pair of distinct vertices, $u,v\in V\setminus L$, there are at least two vertices of $L$ separating them. Such a feasible solution is called a landmark set. We analyze the structure of landmark sets for trees and design a linear time algorithm for finding a minimum cost landmark set for a given tree graph.     

Toll number of the Cartesian and the lexicographic product of graphs

Toll convexity is a variation of the so-called interval convexity. A tolled walk $T$ between two non-adjacent vertices $u$ and $v$ in a graph $G$ is a walk, in which $u$ is adjacent only to the second vertex of $T$ and $v$ is adjacent only to the second-to-last vertex of $T$. A toll interval between $u,v\in V\left(G\right)$ is a set $T_G(u,v)=\{x\in V\left(G\right):x\text{ lies on a tolled walk between }u\text{ and }v\}$. A set $S?V\left(G\right)$ is toll convex, if $T_G(u,v)?S$ for all $u,v\in S$. A toll closure of a set $S?V\left(G\right)$ is the union of toll intervals between all pairs of vertices from $S$. The size of a smallest set $S$ whose toll closure is the whole vertex set is called a toll number of a graph $G$, $tn\left(G\right)$. The first part of the paper reinvestigates the characterization of convex sets in the Cartesian product of two graphs. It is proved that the toll number of the Cartesian product of two graphs equals 2. In the second part, the toll number of the lexicographic product of two graphs is studied. It is shown that if $H$ is not isomorphic to a complete graph, $tn(G°H)\le 3?tn\left(G\right)$. We give some necessary and sufficient conditions for $tn(G°H)=3?tn\left(G\right)$. Moreover, if $G$ has at least two extreme vertices, a complete characterization is given. Furthermore, graphs with $tn(G°H)=2$ are characterized. Finally, the formula for $tn(G°H)$ is given — it is described in terms of the so-called toll-dominating triples or, if $H$ is complete, toll-dominating pairs.     

Some heterochromatic theorems for matroids

The anti-Ramsey number of Erdös, Simonovits and Sós from 1973 has become a classic invariant in Graph Theory. To extend this invariant to Matroid Theory, we use the heterochromatic number $hc\left(H\right)$ of a non-empty hypergraph $H$. The heterochromatic number of $H$ is the smallest integer $k$ such that for every colouring of the vertices of $H$ with exactly $k$ colours, there is a totally multicoloured hyperedge of $H$.Given a matroid $M$, there are several hypergraphs over the ground set of $M$ we can consider, for example, $C\left(M\right)$, whose hyperedges are the circuits of $M$, or $B\left(M\right)$, whose hyperedges are the bases of $M$. We determine $hc\left(C\left(M\right)\right)$ for general matroids and characterise the matroids with the property that $hc\left(B\left(M\right)\right)$ equals the rank of the matroid. We also consider the case when the hyperedges are the Hamiltonian circuits of the matroid. Finally, we extend the known result about the anti-Ramsey number of 3-cycles in complete graphs to the heterochromatic number of 3-circuits in projective geometries over finite fields, and we propose a problem very similar to the famous problem on the anti-Ramsey number of the $p$-cycles.     

On a conjecture about Wiener index in iterated line graphs of trees

Let $G$ be a graph. Denote by $L^i\left(G\right)$ its $i$-iterated line graph and denote by $W\left(G\right)$ its Wiener index. Dobrynin and Melnikov conjectured that there exists no nontrivial tree $T$ and $i\ge 3$, such that $W\left(L^i\left(T\right)\right)=W\left(T\right)$. We prove this conjecture for trees which are not homeomorphic to the claw $K_{1,3}$ and $H$, where $H$ is a tree consisting of 6 vertices, 2 of which have degree 3.     

Toughness,binding number and restricted matching extension in a graph

A connected graph $G$ with at least $2m+2n+2$ vertices is said to satisfy the property $E(m,n)$ if $G$ contains a perfect matching and for any two sets of independent edges $M$ and $N$ with $\left|M\right|=m$ and $\left|N\right|=n$ with $M\cap N=?$, there is a perfect matching $F$ in $G$ such that $M?F$ and $N\cap F=?$. In particular, if $G$ is $E(m,0)$, we say that $G$ is $m$-extendable. One of the authors has proved that every $m$-tough graph of even order at least $2m+2$ is $m$-extendable (Plummer, 1988). Chen (1995) and Robertshaw and Woodall (2002) gave sufficient conditions on binding number for $m$-extendability. In this paper, we extend these results and give lower bounds on toughness and binding number which guarantee $E(m,n)$.     

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.