BZPEER

preprint2022arXiv

Total $k$ -domination in Cartesian product of complete graphs

Let $G=(V,E)$ be a finite undirected graph. A set $S$ of vertices in $V$ is said to be total $k$ -dominating if every vertex in $V$ is adjacent to at least $k$ vertices in $S$ . The total $k$ -domination number, $γ_{kt}(G)$ , is the minimum cardinality of a total $k$ -dominating set in $G$ . In this work we study the total $k$ -domination number of Cartesian product of two complete graphs which is a lower bound of the total $k$ -domination number of Cartesian product of two graphs. We obtain new lower and upper bounds for the total $k$ -domination number of Cartesian product of two complete graphs. Some asymptotic behaviors are obtained as a consequence of the bounds we found. In particular, we obtain that $\displaystyle\liminf_{n\to\infty}\frac{γ_{kt}(G\Box H)}{n}\leq 2\,\left(\left\lceil\frac{k}{2}\right\rceil^{-1}+\left\lfloor\frac{k+4}{2}\right\rfloor^{-1}\right)^{-1}$ for graphs $G,H$ with order at least $n$ . We also prove that the equality is attained if and only if $k$ is even. The equality holds when $G,H$ are both isomorphic to the complete graph, $K_n$ , with $n$ vertices. Furthermore, we obtain closed formulas for the total $2$ -domination number of Cartesian product of two complete graphs of whatever order. Besides, we prove that, for $k=3$ , the inequality above is improvable to $\displaystyle\liminf_{n\to\infty} γ_{3t}(K_n\Box K_n)/n \leq 11/5$ .

preprint2020arXiv

Distinguishing wheel graphs by the alliance polynomial

Distinctive power of the alliance polynomial has been studied in previous works, for instance, it has been proved that the empty, path, cycle, complete, complete without one edge and star graphs are characterized by its alliance polynomial. Moreover, it has been proved that the family of alliance polynomial of regular graphs with small degree is a very special one, since it does not contain alliance polynomial of graphs other than regular graph with the same degree. In this work we prove that the alliance polynomial also determines the wheel graphs.

preprint2020arXiv

Relations between some topological indices and the line graph

The concepts of geometric-arithmetic and harmonic indices were introduced in the area of chemical graph theory recently. They have proven to correlate well with physical and chemical properties of some molecules. The aim of this paper is to obtain new inequalities involving the first Zagreb, the harmonic, and the geometric-arithmetic $GA_1$ indices. Furthermore, inequalities relating these indices and line graphs are proven.

preprint2016arXiv

Cohen-Macaulayness of triangular graphs

We study the Cohen-Macaulay property of triangular graphs $T_n$ . We show that $T_2$ , $T_3$ and $T_5$ are Cohen-Macaulay graphs, and that $T_4$ , $T_6$ , $T_8$ and $T_n$ are not Cohen-Macaulay graphs, for $n\geq 10$ . Finally, we prove that over fields of characteristic zero $T_7$ and $T_9$ are Cohen-Macaulay.

preprint2016arXiv

Hyperbolicity of direct products of graphs

If $X$ is a geodesic metric space and $x_1,x_2,x_3\in X$ , a {\it geodesic triangle} $T=\{x_1,x_2,x_3\}$ is the union of the three geodesics $[x_1x_2]$ , $[x_2x_3]$ and $[x_3x_1]$ in $X$ . The space $X$ is $δ$ -\emph{hyperbolic} $($ in the Gromov sense $)$ if any side of $T$ is contained in a $δ$ -neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$ . If $X$ is hyperbolic, we denote by $δ(X)$ the sharp hyperbolicity constant of $X$ , i.e., $δ(X)=\inf\{δ\ge 0: \, X \, \text{ is $δ$-hyperbolic}\,\}.$ Some previous works characterize the hyperbolic product graphs (for the Cartesian, strong, join, corona and lexicographic products) in terms of properties of the factor graphs. However, the problem with the direct product is more complicated. In this paper, we prove that if the direct product $G_1\times G_2$ is hyperbolic, then one factor is hyperbolic and the other one is bounded. Also, we prove that this necessary condition is, in fact, a characterization in many cases. In other cases, we find characterizations which are not so simple. Furthermore, we obtain formulae or good bounds for the hyperbolicity constant of the direct product of some important graphs.

preprint2015arXiv

Alliance polynomial of regular graphs

The alliance polynomial of a graph $G$ with order $n$ and maximum degree $Δ$ is the polynomial $A(G; x) = \sum_{k=-Δ}^Δ A_{k}(G) \, x^{n+k}$ , where $A_{k}(G)$ is the number of exact defensive $k$ -alliances in $G$ . We obtain some properties of $A(G; x)$ and its coefficients for regular graphs. In particular, we characterize the degree of regular graphs by the number of non-zero coefficients of their alliance polynomial. Besides, we prove that the family of alliance polynomials of $Δ$ -regular graphs with small degree is a very special one, since it does not contain alliance polynomials of graphs which are not $Δ$ -regular. By using this last result and direct computation we find that the alliance polynomial determines uniquely each cubic graph of order less than or equal to $10$ .

preprint2015arXiv

Computing the strong alliance polynomial of a graph

We introduce the strong alliance polynomial of a graph. The strong alliance polynomial of a graph $G$ with order n and strong defensive alliance number $a(G)$ is the polynomial $a(G;x):=\sum_{i=a(G)}^{n}\, a_i(G)\ x^i$ , where $a_{k}(G)$ is the number of strong defensive alliances with cardinality $k$ in $G$ . We obtain some properties of $a(G; x)$ and its coefficients. In particular, we compute strong alliance polynomial for path, cycle, complete, start, complete bipartite and double star graphs; some of them verify unimodality.

preprint2015arXiv

Gromov hyperbolicity in lexicographic product graphs

If $X$ is a geodesic metric space and $x_1,x_2,x_3\in X$ , a {\it geodesic triangle} $T=\{x_1,x_2,x_3\}$ is the union of the three geodesics $[x_1x_2]$ , $[x_2x_3]$ and $[x_3x_1]$ in $X$ . The space $X$ is $δ$ -\emph{hyperbolic} $($ in the Gromov sense $)$ if any side of $T$ is contained in a $δ$ -neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$ . If $X$ is hyperbolic, we denote by $δ(X)$ the sharp hyperbolicity constant of $X$ , i.e. $δ(X)=\inf\{δ\ge 0: \, X \, \text{ is $δ$-hyperbolic}\}.$ In this paper we characterize the lexicographic product of two graphs $G_1\circ G_2$ which are hyperbolic, in terms of $G_1$ and $G_2$ : the lexicographic product graph $G_1\circ G_2$ is hyperbolic if and only if $G_1$ is hyperbolic, unless if $G_1$ is a trivial graph (the graph with a single vertex); if $G_1$ is trivial, then $G_1\circ G_2$ is hyperbolic if and only if $G_2$ is hyperbolic. In particular, we obtain the sharp inequalities $δ(G_1)\le δ(G_1\circ G_2) \le δ(G_1) + 3/2$ if $G_1$ is not a trivial graph, and we characterize the graphs for which the second inequality is attained.

preprint2015arXiv

Gromov hyperbolicity of minor graphs

If $X$ is a geodesic metric space and $x_1,x_2,x_3\in X$ , a geodesic triangle $T=\{x_1,x_2,x_3\}$ is the union of the three geodesics $[x_1x_2]$ , $[x_2x_3]$ and $[x_3x_1]$ in $X$ . The space $X$ is $δ$ -hyperbolic (in the Gromov sense) if any side of $T$ is contained in a $δ$ -neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$ . The study of hyperbolic graphs is an interesting topic since the hyperbolicity of a geodesic metric space is equivalent to the hyperbolicity of a graph related to it. In the context of graphs, to remove and to contract an edge of a graph are natural transformations. The main aim in this work is to obtain quantitative information about the distortion of the hyperbolicity constant of the graph $G \setminus e$ (respectively, $\,G/e\,$ ) obtained from the graph $G$ by deleting (respectively, contracting) an arbitrary edge $e$ from it. This work provides information about the hyperbolicity constant of minor graphs.

preprint2015arXiv

Solving a conjecture about tessellation graphs of $\mathbb R^2$

In the paper Planarity and Hyperbolicity in Graphs, the authors present the following conjecture: every tessellation of the Euclidean plane with convex tiles induces a non-hyperbolic graph. It is natural to think that this statement holds since the Euclidean plane is non-hyperbolic. Furthermore, there are several results supporting this conjecture. However, this work shows that the conjecture is false.

preprint2014arXiv

Computing the alliance polynomial of a graph

The alliance polynomial of a graph $Γ$ with order $n$ and maximum degree $δ_1$ is the polynomial $A(Γ; x) = \sum_{k=-δ_1}^{δ_1} A_{k}(Γ) \, x^{n+k}$ , where $A_{k}(Γ)$ is the number of exact defensive $k$ -alliances in $Γ$ . We provide an algorithm for computing the alliance polynomial. Furthermore, we obtain some properties of $A(Γ; x)$ and its coefficients. In particular, we prove that the path, cycle, complete and star graphs are characterized by their alliance polynomials. We also show that the alliance polynomial characterizes many graphs that are not distinguished by other usual polynomials of graphs.

preprint2014arXiv

Hyperbolicity in the corona and join of graphs

If X is a geodesic metric space and $x_1,x_2,x_3\in X$ , a {\it geodesic triangle} $T=\{x_1,x_2,x_3\}$ is the union of the three geodesics $[x_1x_2]$ , $[x_2x_3]$ and $[x_3x_1]$ in $X$ . The space $X$ is $δ$ -\emph{hyperbolic} $($ in the Gromov sense $)$ if any side of $T$ is contained in a $δ$ -neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$ . If $X$ is hyperbolic, we denote by $δ(X)$ the sharp hyperbolicity constant of $X$ , i.e. $δ(X)=\inf\{δ\ge 0: \, X \, \text{ is $δ$-hyperbolic}\,\}\,.$ Some previous works characterize the hyperbolic product graphs (for the Cartesian product, strong product and lexicographic product) in terms of properties of the factor graphs. In this paper we characterize the hyperbolic product graphs for graph join $G_1\uplus G_2$ and the corona $G_1\diamond G_2$ : $G_1\uplus G_2$ is always hyperbolic, and $G_1\diamond G_2$ is hyperbolic if and only if $G_1$ is hyperbolic. Furthermore, we obtain simple formulae for the hyperbolicity constant of the graph join $G_1\uplus G_2$ and the corona $G_1\diamond G_2$ .

preprint2014arXiv

New inequalities on the hyperbolicity constant of line graphs

If X is a geodesic metric space and $x_1,x_2,x_3\in X$ , a {\it geodesic triangle} $T=\{x_1,x_2,x_3\}$ is the union of the three geodesics $[x_1x_2]$ , $[x_2x_3]$ and $[x_3x_1]$ in $X$ . The space $X$ is $δ$ -\emph{hyperbolic} $($ in the Gromov sense $)$ if any side of $T$ is contained in a $δ$ -neighborhood of the union of the two other sides, for every geodesic triangle $T$ in $X$ . We denote by $δ(X)$ the sharp hyperbolicity constant of $X$ , i.e. $δ(X):=\inf\{δ\ge 0: \, X \, \text{ is $δ$-hyperbolic}\,\}\,. $ The main result of this paper is the inequality $δ(G) \le δ(\mathcal L(G))$ for the line graph $\mathcal L(G)$ of every graph $G$ . We prove also the upper bound $δ(\mathcal L(G)) \le 5 δ(G)+ 3 l_{max}$ , where $l_{max}$ is the supremum of the lengths of the edges of $G$ . Furthermore, if every edge of $G$ has length $k$ , we obtain $δ(G) \le δ(\mathcal L(G)) \le 5 δ(G)+ 5k/2$ .

Walter Carballosa

Research overview

Is this your work?

13 publications

Total $k$ -domination in Cartesian product of complete graphs

Distinguishing wheel graphs by the alliance polynomial

Relations between some topological indices and the line graph

Cohen-Macaulayness of triangular graphs

Hyperbolicity of direct products of graphs

Alliance polynomial of regular graphs

Computing the strong alliance polynomial of a graph

Gromov hyperbolicity in lexicographic product graphs

Gromov hyperbolicity of minor graphs

Solving a conjecture about tessellation graphs of $\mathbb R^2$

Computing the alliance polynomial of a graph

Hyperbolicity in the corona and join of graphs

New inequalities on the hyperbolicity constant of line graphs

See the researcher in context

Building this map preview

Walter Carballosa

Research overview

Is this your work?

13 publications

Total kkk-domination in Cartesian product of complete graphs

Distinguishing wheel graphs by the alliance polynomial

Relations between some topological indices and the line graph

Cohen-Macaulayness of triangular graphs

Hyperbolicity of direct products of graphs

Alliance polynomial of regular graphs

Computing the strong alliance polynomial of a graph

Gromov hyperbolicity in lexicographic product graphs

Gromov hyperbolicity of minor graphs

Solving a conjecture about tessellation graphs of R2\mathbb R^2R2

Computing the alliance polynomial of a graph

Hyperbolicity in the corona and join of graphs

New inequalities on the hyperbolicity constant of line graphs

See the researcher in context

Building this map preview

Total $k$ -domination in Cartesian product of complete graphs

Solving a conjecture about tessellation graphs of $\mathbb R^2$