Source author record

J. M. Sigarreta

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

8works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

On the hyperbolicity constant of circular-arc graphs

Gromov hyperbolicity is an interesting geometric property, and so it is natural to study it in the context of geometric graphs. It measures the tree-likeness of a graph from a metric viewpoint. In particular, we are interested in circular-arc graphs, which is an important class of geometric intersection graphs. In this paper we give sharp bounds for the hyperbolicity constant of (finite and infinite) circular-arc graphs. Moreover, we obtain bounds for the hyperbolicity constant of the complement and line of any circular-arc graph. In order to do that, we obtain new results about regular, chordal and line graphs which are interesting by themselves.

preprint2016arXiv

New inequalities involving the Geometric-Arithmetic index

Let $G=(V,E)$ be a simple connected graph and $d_i$ be the degree of its $i$ th vertex. In a recent paper [J. Math. Chem. 46 (2009) 1369-1376] the first geometric-arithmetic index of a graph $G$ was defined as $GA_1=\sum_{ij\in E}\frac{2 \sqrt{d_i d_j}}{d_i + d_j}.$ This graph invariant is useful for chemical proposes. The main use of $GA_1$ is for designing so-called quantitative structure-activity relations and quantitative structure-property relations. In this paper we obtain new inequalities involving the geometric-arithmetic index $GA_1$ and characterize the graphs which make the inequalities tight. In particular, we improve some known results, generalize other, and we relate $GA_1$ to other well-known topological indices.

preprint2013arXiv

On the Randić index and conditional parameters of a graph

The aim of this paper is to study some parameters of simple graphs related with the degree of the vertices. So, our main tool is the $n\times n$ matrix ${\cal A}$ whose ( $i,j$ )-entry is $a_{ij}= \left\lbrace \begin{array}{ll} \frac{1}{\sqrt{δ_iδ_j}} & {\rm if }\quad v_i\sim v_j ; \\ 0 & {\rm otherwise,} \end{array} \right.$ where $δ_i$ denotes the degree of the vertex $v_i$ . We study the Randić index and some interesting particular cases of conditional excess, conditional Wiener index, and conditional diameter. In particular, using the matrix ${\cal A}$ or its eigenvalues, we obtain tight bounds on the studied parameters.

preprint2010arXiv

Global defensive k-alliances in graphs

Let $Γ=(V,E)$ be a simple graph. For a nonempty set $X\subseteq V$ , and a vertex $v\in V$ , $δ_{X}(v)$ denotes the number of neighbors $v$ has in $X$ . A nonempty set $S\subseteq V$ is a \emph{defensive $k$ -alliance} in $Γ=(V,E)$ if $δ_S(v)\ge δ_{\bar{S}}(v)+k,$ $\forall v\in S.$ A defensive $k$ -alliance $S$ is called \emph{global} if it forms a dominating set. The \emph{global defensive $k$ -alliance number} of $Γ$ , denoted by $γ_{k}^{a}(Γ)$ , is the minimum cardinality of a defensive $k$ -alliance in $Γ$ . We study the mathematical properties of $γ_{k}^{a}(Γ)$ .

preprint2008arXiv

Alliance free and alliance cover sets

A \emph{defensive} (\emph{offensive}) $k$ -\emph{alliance} in $Γ=(V,E)$ is a set $S\subseteq V$ such that every $v$ in $S$ (in the boundary of $S$ ) has at least $k$ more neighbors in $S$ than it has in $V\setminus S$ . A set $X\subseteq V$ is \emph{defensive} (\emph{offensive}) $k$ -\emph{alliance free,} if for all defensive (offensive) $k$ -alliance $S$ , $S\setminus X\neq\emptyset$ , i.e., $X$ does not contain any defensive (offensive) $k$ -alliance as a subset. A set $Y \subseteq V$ is a \emph{defensive} (\emph{offensive}) $k$ -\emph{alliance cover}, if for all defensive (offensive) $k$ -alliance $S$ , $S\cap Y\neq\emptyset$ , i.e., $Y$ contains at least one vertex from each defensive (offensive) $k$ -alliance of $Γ$ . In this paper we show several mathematical properties of defensive (offensive) $k$ -alliance free sets and defensive (offensive) $k$ -alliance cover sets, including tight bounds on the cardinality of defensive (offensive) $k$ -alliance free (cover) sets.

preprint2007arXiv

Offensive k-alliances in graphs

Let $G=(V,E)$ be a simple graph. For a nonempty set $X\subset V,$ and a vertex $v\in V,$ $δ_{X}(v)$ denotes the number of neighbors $v$ has in $X.$ A nonempty set $S\subset V$ is an \emph{offensive $r$ -alliance} in $G$ if $δ_S(v)\ge δ_{\bar{S}}(v)+r,$ $\forall v\in \partial (S),$ where $\partial (S)$ denotes the boundary of $S$ . An offensive $r$ -alliance $S$ is called \emph{global} if it forms a dominating set. The \emph{global offensive $r$ -alliance number} of $G$ , denoted by $γ_{r}^{o}(G)$ , is the minimum cardinality of a global offensive $r$ -alliance in $G$ . We show that the problem of finding optimal (global) offensive $r$ -alliances is NP-complete and we obtain several tight bounds on $γ_{r}^{o}(G)$ .

preprint2006arXiv

Offensive alliances in cubic graphs

An offensive alliance in a graph $Γ=(V,E)$ is a set of vertices $S\subset V$ where for every vertex $v$ in its boundary it holds that the majority of vertices in $v$ 's closed neighborhood are in $S$ . In the case of strong offensive alliance, strict majority is required. An alliance $S$ is called global if it affects every vertex in $V\backslash S$ , that is, $S$ is a dominating set of $Γ$ . The global offensive alliance number $γ_o(Γ)$ (respectively, global strong offensive alliance number $γ_{\hat{o}}(Γ)$ ) is the minimum cardinality of a global offensive (respectively, global strong offensive) alliance in $Γ$ . If $Γ$ has global independent offensive alliances, then the \emph{global independent offensive alliance number} $γ_i(Γ)$ is the minimum cardinality among all independent global offensive alliances of $Γ$ . In this paper we study mathematical properties of the global (strong) alliance number of cubic graphs. For instance, we show that for all connected cubic graph of order $n$ , $\frac{2n}{5}\le γ_i(Γ)\le \frac{n}{2}\le γ_{\hat{o}}(Γ)\le \frac{3n}{4} \le γ_{\hat{o}}({\cal L}(Γ))=γ_{o}({\cal L}(Γ))\le n,$ where ${\cal L}(Γ)$ denotes the line graph of $Γ$ . All the above bounds are tight.

preprint2006arXiv

On the global offensive alliance number of a graph

An offensive alliance in a graph $Γ=(V,E)$ is a set of vertices $S\subset V$ where for every vertex $v$ in its boundary it holds that the majority of vertices in $v$ 's closed neighborhood are in $S$ . In the case of strong offensive alliance, strict majority is required. An alliance $S$ is called global if it affects every vertex in $V\backslash S$ , that is, $S$ is a dominating set of $Γ$ . The offensive alliance number $a_o(Γ)$ (respectively, strong offensive alliance number $a_{\hat{o}}(Γ)$ ) is the minimum cardinality of an offensive (respectively, strong offensive) alliance in $Γ$ . The global offensive alliance number $γ_o(Γ)$ and the global strong offensive alliance number $γ_{\hat{o}}(Γ)$ are defined similarly. Clearly, $a_o(Γ)\le γ_o(Γ)$ and $a_{\hat{o}}(Γ)\le γ_{\hat{o}}(Γ)$ . It was shown in [Discuss. Math. Graph Theory, 24 (2004), no. 2, 263-275] that $a_o(Γ)\le \frac{2n}{3}$ and $a_{\hat{o}}(Γ)\le \frac{5n}{6}$ , where $n$ denotes the order of $Γ$ . In this paper we obtain several tight bounds on $γ_o(Γ)$ and $γ_{\hat{o}}(Γ)$ in terms of several parameters of $Γ$ . For instance, we show that $\frac{2m+n}{3Δ+1} \le γ_o(Γ)\le \frac{2n}{3}$ and $\frac{2(m+n)}{3Δ+2} \leγ_{\hat{o}}(Γ)\le \frac{5n}{6}$ , where $m$ denotes the size of $Γ$ and $Δ$ its maximum degree (the last upper bound holds true for all $Γ$ with minimum degree greatest or equal to two).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.