Mustapha Aouchiche
BackPublications
Cahiers du GERAD
For a simple connected graph \(G\)
, let \(D(G), ~Tr(G)\)
, \(D^{L}(G)=Tr(G)-D(G)\)
, and \(D^{Q}(G)=Tr(G)+D(G)\)
be the distance matrix, the diagonal m...
For a graph \(G\)
, the signless Laplacian matrix \(Q(G)\)
defined as \(Q(G) = D(G) + A(G)\)
, where \(A(G)\)
is the adjacency matrix of \(G\)
and `...
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...
BibTeX reference
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...
Let \({\mathcal D(G)}\)
, \({\mathcal D}^L(G)={\mathcal Diag(Tr)} - {\mathcal D(G)}\)
and \({\mathcal D}^Q(G)={\mathcal Diag(Tr)} + {\mathcal D(G)}\)
b...
Let \(G\)
be a graph of order \(n\)
. The energy \(\mathcal{E}(G)\)
of a simple graph \(G\)
is the sum of
absolute values of the eigenvalues of its ...
Necessary and sufficient conditions are provided for the existence of a simple
graph, or a simple connected graph with given
numbers \(m_{ij}\)
of edges ...
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 ...
BibTeX reference
Graph theoretical heuristics are used extensively in many fields to solve approximately large scale optimization problems. Graph theoretical heuristics can a...
BibTeX reference
In the present paper we are interested in the study of the distance Laplacian eigenvalues of a connected graph with fixed order \(n\)
and chromatic number ...
The geometric-arithmetic index \(GA\)
of a graph \(G\)
is the sum of ratios, over all edges of \(G\)
, of the geometric mean to the arithmetic mean of t...
In the present paper, we prove lower and upper bounds for each of the ratios \(GA/\delta\)
, \(GA/\overline{d}\)
and \(\Delta\)
, in terms of the order `...
In the present paper, we compare the geometric-arithmetic index \(GA\)
and the chromatic number \(\chi\)
of a connected graph with given order. We prove,...
In the present paper, we are interested in bounding differences between graph invariants as well as in characterizing the corresponding extremal graphs. This...
BibTeX reference
The distance signless Laplacian of a connected graph \(G\)
is defined by \(\mathcal{D}^\mathcal{Q} = Diag(Tr) + \mathcal{D}\)
, where \(\mathcal{D}\)
is...
Proximity \(\pi\)
and remoteness \(\rho\)
are respectively the minimum and the maximum, over the vertices of a connected graph, of the average distance f...
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...
BibTeX reference
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...
BibTeX reference
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...
BibTeX reference
Introduced during the late nineties of the last century, Variable Neighborhood Search (VNS) was first designed for solving specific problems in combinatorial...
BibTeX reference
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...
BibTeX reference
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...
BibTeX reference
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...
BibTeX reference
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...
BibTeX reference
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...
BibTeX referenceThe 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...
BibTeX reference
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...
BibTeX reference
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...
BibTeX reference
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 ...
BibTeX referenceOn 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...
BibTeX reference
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...
BibTeX reference
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...
BibTeX reference
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...
BibTeX reference
The AutoGraphiX system (AGX 1 and AGX 2) for interactive, and for several functions automated, graph theory, discovers conjectures of algebraic or structura...
BibTeX reference
<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...
BibTeX referenceVariable 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:...
BibTeX reference
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 ...
BibTeX reference
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"...
BibTeX reference
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...
BibTeX reference
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...
BibTeX referenceVariable 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...
BibTeX reference
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 ...
BibTeX reference
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...
BibTeX reference
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...
BibTeX referenceVariable 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...
BibTeX referenceOn 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...
BibTeX reference
<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...
BibTeX reference
<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 ...
BibTeX referenceAutoGraphiX: A Survey
A survey is made of the AutoGraphiX (AGX) research program for computer as- sisted and, for some functions, automated graph theory.
BibTeX reference
The AutoGraphiX (AGX) system for computer assisted or, for some of its functions, fully automated graph theory was developed at GERAD, Montreal since 1997. ...
BibTeX reference
Conjectures in graph theory have multiple forms and involve graph invariants, graph classes, subgraphs, minors and other concepts in premisses and/or conclu...
BibTeX reference
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 ...
BibTeX reference