Mustapha Aouchiche
RetourPublications
Cahiers du GERAD
Pour un graphe simple et connexe \(G\)
, soient \(D(G), ~Tr(G)\)
, \(D^{L}(G)=Tr(G)-D(G)\)
, et \(D^{Q}(G)=Tr(G)+D(G)\)
la matrice des distances, la mat...
Pour un graphe \(G\)
, la matrice du laplacien sans signe \(Q(G)\)
esf définie comme \(Q(G) = D(G) + A(G)\)
, o`u \(A(G)\)
est la matrice d'adjacence ...
Spectral properties of threshold graphs
In this paper we study the spectral properties of the threshold graphs. In particular, we give lower and upper bounds for the largest and smallest eigenvalue...
référence BibTeX
In the present paper, we prove lower and upper bounds for each of the ratios \(GA/\delta\)
, as well as a lower bound on \(GA/\sqrt{\delta}\)
, in terms of...
Soient \({\mathcal D(G)}\)
, \({\mathcal D}^L(G)={\mathcal Diag(Tr)} - {\mathcal D(G)}\)
et \({\mathcal D}^Q(G)={\mathcal Diag(Tr)} + {\mathcal D(G)}\)
,...
Soit \(G\)
un graph d'ordre \(n\)
. L'énergie \(\mathcal{E}(G)\)
d'un graph simple \(G\)
est la somme de des valeurs absolues des valeurs propres de s...
Nous donnons des conditions nécessaires et suffisante pour l'existence d'un graphe simple, ou d'un graphe connexe simple, ayant des nombres donnés `(m_{ij}...
référence BibTeX
The distance, distance Laplacian and distance signless Laplacian spectra of a connected graph \(G\)
are the spectra of the distance, distance Laplacian and...
On the nullity number of graphs
The paper discusses bounds on the nullity number of graphs. It is proved in [B. Cheng and B. Liu, On the nullity of graphs. Electron. J. Linear Algebra 16 ...
référence BibTeX
Les heuristiques basées sur la théorie des graphes sont largement utilisées dans plusieurs domaines pour résoudre approximativement des problèmes d'optimisat...
référence BibTeX
Dans cet article, nous nous intéressons à létude des valeurs propres du laplacien des distances d'un graphe connexe d'ordre \(n\)
et de nombre chromatique ...
L'indice géométrique-arithmétique \(GA\)
d'un graphe \(G\)
est la somme des ratios, sur l'ensemble des arêtes de \(G\)
, de la moyenne géométrique sur l...
Dans le présent article, nous démontrons des bornes inférieure et supérieure sur chacun des rapports \(GA/\delta\)
, \(GA/\overline{d}\)
et \(\Delta\)
, ...
Dans le présent article, nous comparons l'indice géométrique-arithmétique \(GA\)
et le nombre chromatique \(\chi\)
d'un graphe connexe d'ordre donné. Ent...
In the present paper, we are interested in bounding differences between graph invariants as well as in characterizing the corresponding extremal graphs. This...
référence BibTeX
Le laplacien sans signe des distances d'un graphe connexe \(G\)
est défini par \(\mathcal{D}^\mathcal{Q} = Diag(Tr) + \mathcal{D}\)
, où \(\mathcal{D}\)
...
La proximité \(\pi\)
et l'éloignement \(\rho\)
sont respectivement le minimum et le maximum, pour les sommets d'un graphe connexe, de la distance moyenne...
Distance Spectra of Graphs: A Survey
In 1971, Graham and Pollack established a relationship between the number of negative eigenvalues of the distance matrix and the addressing problem in data c...
référence BibTeX
The distance Laplacian of a connected graph G is defined by L = Diag(Tr) - D, where D is the distance matrix of G , and Diag(Tr) is the diagonal m...
référence BibTeX
In the present paper, we are interested in studying mathematical properties of the Balaban index of connected graphs. We present a discussion on and refuta...
référence BibTeX
Introduced during the late nineties of the last century, Variable Neighborhood Search (VNS) was first designed for solving specific problems in combinatorial...
référence BibTeX
We introduce a Laplacian and a signless Laplacian for the distance matrix of a connected graph, called the <i>distance Laplacian</i> and <i>distance signless...
référence BibTeX
Since the late forties of the last century, methods of operations research have been extensively used to solve problems in graph theory, and graph theory has...
référence BibTeX
We introduce a signless Laplacian for the distance matrix of a connected graph, called the <i>distance signless Laplacian</i>. We study the <i>distance signl...
référence BibTeX
We introduce a Laplacian for the distance matrix of a connected graph, called the <i>distance Laplacian</i> and we study its spectrum. We show the equivalenc...
référence BibTeX
In 1956, Nordhaus and Gaddum gave lower and upper bounds on the sum and the product of the chromatic number of a graph and its complement, in terms of the or...
référence BibTeXThe Normalized Revised Szeged Index
In chemical graph theory, many graph parameters, or topological indices, were proposed as estimators of molecular structural properties. Often several varian...
référence BibTeX
We study extremal graphs for the extremal values of the second largest <i>Q</i>-eigenvalue of a connected graph. We first characterize all simple connected g...
référence BibTeX
Let <i>G</i> be a connected graph of order <i>n</i>. The algebraic connectivity of <i>G</i> is the second smallest eigenvalue of the Laplacian matrix of <i>G...
référence BibTeX
The <i>proximity</i> <img src="/cgi-bin/mimetex.cgi?\pi = \pi (G)"> of a connected graph <i>G</i> is the minimum, over all vertices, of the average distance ...
référence BibTeXOn a Conjecture About the Szeged Index
Khalifeh, Yousefi-Azari, Ashrafi and Wagner [European J. Combin. 30 (2009) 1149-1163] conjectured that for a connected graph <i>G</i> on <i>n</i> vertices...
référence BibTeX
The proximity <img src="/cgi-bin/mimetex.cgi?\pi"> of a graph <i>G</i> is the minimum average distance from a vertex of <i>G</i> to all others. Similarly, th...
référence BibTeX
During the last three decades, the computer has been widely used in spectral graph theory. Many results about graph eigenvalues were first conjectured, and i...
référence BibTeX
Upper bounds on the average distance \(\overline{l}\)
between pairs of vertices of a connected graph with given order \(n\)
and minimum degree `(\delta...
The transmission of a vertex in a connected graph is the sum of all distance from that vertex to the others. It is said to be normalized if divided by <i>n-1...
référence BibTeX
The AutoGraphiX system (AGX 1 and AGX 2) for interactive, and for several functions automated, graph theory, discovers conjectures of algebraic or structura...
référence BibTeX
<p>On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme </p>
<p><center> <img src="/cgi-bin/mimetex.cgi?\underline{b}_{n} \, \l...
référence BibTeXVariable Neighborhood Search for Extremal Graphs. 25. Products of Connectivity and Distance Measures
Upper bounds for products of four measures of distances in graphs: diameter, radius, average eccentricity and remoteness with three measures of connectivity:...
référence BibTeX
In the set of all connected graphs with a given domination number, we characterize the graphs which achieve the maximum value of the spectral radius of the ...
référence BibTeX
A set of vertices <i>S</i> in a graph <i>G</i> is a clique if any two of its vertices are adjacent. The clique number <img src="/cgi-bin/mimetex.cgi?\omega"...
référence BibTeX
A set of vertices <i>S</i> in a graph <i>G</i> is independent if no neighbor of a vertex of <i>S</i> belongs to <i>S</i>. A set of vertices <i>U</i> in a gr...
référence BibTeX
The AutoGraphiX 2 system is used to compare the index of a graph <i>G</i> with a number of other graph theoretical invariants, i.e., chromatic number, maxim...
référence BibTeXVariable Neighborhood Search for Extremal Graphs. 20. Automated Comparison of Graph Invariants
A graph invariant is a function of a graph <i>G</i> which does not depend on labeling of <i>G</i>’s vertices or edges. An algebraic expression of one or sev...
référence BibTeX
A set of vertices <i>S</i> in a graph <i>G</i> is independent if no neighbor of a vertex of <i>S</i> belongs to <i>S</i>. The independence number &alpha is ...
référence BibTeX
We consider four conjectures related to the largest eigenvalue of (the adjacency matrix of) a graph (i.e., to the index of the graph). Three of them have be...
référence BibTeX
The AutoGraphiX research program led to a new type of application of metaheuristics in graph theory, <i>i.e.</i>, finding conjectures on graph invariants by...
référence BibTeXVariable Neighborhood Search for Extremal Graphs. 18. Conjectures and Results about the Randic Index
Using the AutoGraphiX 2 system (AGX2), we study relations between graph invariants of the form <img src="/cgi-bin/mimetex.cgi?lbn \leq R \oplus i \leq ub...
référence BibTeXOn a Conjecture About the Randic Index
A conjecture of Delorme, Favaron and Rautenbach [DM 257 (2002) 29-38] about the Randic index of a graph, in relation to its order and minimum degree, is ref...
référence BibTeX
<p>Le système <i>AutoGraphiX (AGX1 et AGX2)</i> permet, parmi d’autres fonctions, la génération automatique de conjectures en théorie des graphes. Nous étud...
référence BibTeX
<p>Using the <i>AutoGraphiX 2</i> system, a systematic study is made on generation and proof of relations of the form</p> <center> $\underline{b}_n \leq ...
référence BibTeXAutoGraphiX: A Survey
A survey is made of the AutoGraphiX (AGX) research program for computer as- sisted and, for some functions, automated graph theory.
référence BibTeX
The AutoGraphiX (AGX) system for computer assisted or, for some of its functions, fully automated graph theory was developed at GERAD, Montreal since 1997. ...
référence BibTeX
Conjectures in graph theory have multiple forms and involve graph invariants, graph classes, subgraphs, minors and other concepts in premisses and/or conclu...
référence BibTeX
Graffiti's conjecture 105 states that for any tree the range of transmissions of distance is greater than or equal to the range of degrees. After using the ...
référence BibTeX