Source author record

Domingos M. Cardoso

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

ResearcherUnclaimed source record

math.CO math.AC

Catalog footprint

Research overview

6works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Sharp bounds on the least eigenvalue of a graph determined from edge clique partitions

Sharp bounds on the least eigenvalue of an arbitrary graph are presented. Necessary and sufficient (just sufficient) conditions for the lower (upper) bound to be attained are deduced using edge clique partitions. As an application, we prove that the least eigenvalue of the $n$ -Queens' graph $\mathcal{Q}(n)$ is equal to $-4$ for every $n \ge 4$ and it is also proven that the multiplicity of this eigenvalue is $(n-3)^2$ . Additionally, some results on the edge clique partition graph parameters are obtained.

preprint2021arXiv

The H-join of arbitrary families of graphs

The $H$ -join of a family of graphs $\mathcal{G}=\{G_1, \dots, G_p\}$ , also called the generalized composition, $H[G_1, \dots, G_p]$ , where all graphs are undirected, simple and finite, is the graph obtained by replacing each vertex $i$ of $H$ by $G_i$ and adding to the edges of all graphs in $\mathcal{G}$ the edges of the join $G_i \vee G_j$ , for every edge $ij$ of $H$ . Some well known graph operations are particular cases of the $H$ -join of a family of graphs $\mathcal{G}$ as it is the case of the lexicographic product (also called composition) of two graphs $H$ and $G$ , $H[G]$ . During long time the known expressions for the determination of the entire spectrum of the $H$ -join in terms of the spectra of its components and an associated matrix were limited to families of regular graphs. In this work, we extend such a determination, as well as the determination of the characteristic polynomial, to families of arbitrary graphs. From the obtained results, the eigenvectors of the adjacency matrix of the $H$ -join can also be determined in terms of the adjacency matrices of the components and an associated matrix.

preprint2016arXiv

Laplacian Distribution and Domination

Let $m_G(I)$ denote the number of Laplacian eigenvalues of a graph $G$ in an interval $I$ , and let $γ(G)$ denote its domination number. We extend the recent result $m_G[0,1) \leq γ(G)$ , and show that isolate-free graphs also satisfy $γ(G) \leq m_G[2,n]$ . In pursuit of better understanding Laplacian eigenvalue distribution, we find applications for these inequalities. We relate these spectral parameters with the approximability of $γ(G)$ , showing that $\frac{γ(G)}{m_G[0,1)} \not\in O(\log n)$ . However, $γ(G) \leq m_G[2, n] \leq (c + 1) γ(G)$ for $c$ -cyclic graphs, $c \geq 1$ . For trees $T$ , $γ(T) \leq m_T[2, n] \leq 2 γ(G)$ .

preprint2015arXiv

Injective Edge Chromatic Index of a Graph

Three edges $e_{1}, e_{2}$ and $e_{3}$ in a graph $G$ are consecutive if they form a path (in this order) or a cycle of length three. An injective edge coloring of a graph $G = (V,E)$ is a coloring $c$ of the edges of $G$ such that if $e_{1}, e_{2}$ and $e_{3}$ are consecutive edges in $G$ , then $c(e_{1})\neq c(e_3)$ . The injective edge coloring number $χ_{i}^{'}(G)$ is the minimum number of colors permitted in such a coloring. In this paper, exact values of $χ_{i}^{'}(G)$ for several classes of graphs are obtained, upper and lower bounds for $χ_{i}^{'}(G)$ are introduced and it is proven that checking whether $χ_{i}^{'}(G)= k$ is NP-complete.

preprint2013arXiv

Spectral results for the dominating induced matching problem

A matching M is a dominating induced matching of a graph, if every edge of the graph is either in $M$ or has a common end-vertex with exactly one edge in $M$ . The concept of complete dominating induced matching is introduced as graphs where the vertex set can be partitioned into two subsets, one of them inducing an $1$ -regular graph and the other defining an independent set and such that all the remaining edges connect each vertex of one set to each vertex of the other. The principal eigenvectors of the adjacency, Laplacian and signless Laplacian matrices of graphs with complete dominating induced matchings are characterized and, therefore, the polynomial time recognition of graphs with complete dominating induced matchings is stated. The adjacency, Laplacian and signless Laplacian spectrum of graphs with complete dominating induced matchings are characterized. Finally, several upper and lower bounds on the cardinality of a dominating induced matching obtained from the eigenvalues of the adjacency, Laplacian and signless Laplacian matrices are deduced and examples for which some of these bounds are tight are presented.

preprint2012arXiv

Eigenvalues of a H-generalized join graph operation constrained by vertex subsets

Considering a graph $H$ of order $p$ , a generalized $H$ -join operation of a family of graphs $G_1,..., G_p$ , constrained by a family of vertex subsets $S_i \subseteq V(G_i)$ , $i=1,..., p,$ is introduced. When each vertex subset $S_i$ is $(k_i,τ_i)$ -regular, it is deduced that all non-main adjacency eigenvalues of $G_i$ , different from $k_i-τ_i$ , for $i=1,..., p,$ remain as eigenvalues of the graph $G$ obtained by the above mentioned operation. Furthermore, if each graph $G_i$ of the family is $k_i$ -regular, for $i=1,..., p$ , and all the vertex subsets are such that $S_i=V(G_i)$ , the $H$ -generalized join operation constrained by these vertex subsets coincides with the $H$ -generalized join operation. Some applications on the spread of graphs are presented. Namely, new lower and upper bounds are deduced and a infinity family of non regular graphs of order $n$ with spread equals $n$ is introduced.

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.