Variable neighborhood search for extremal graphs. I: The AutoGraphiX system
From MaRDI portal
Publication:1970574
DOI10.1016/S0012-365X(99)00206-XzbMath0947.90130OpenAlexW1998140754MaRDI QIDQ1970574
Gilles Caporossi, Pierre Hansen
Publication date: 8 November 2000
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0012-365x(99)00206-x
Extremal problems in graph theory (05C35) Approximation methods and heuristics in mathematical programming (90C59)
Related Items (96)
On the further relation between the (revised) Szeged index and the Wiener index of graphs ⋮ Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs ⋮ Problems of discrete optimization: challenges and main approaches to solve them ⋮ Eccentricity-based topological indices of a cyclic octahedron structure ⋮ Proximity, remoteness and distance eigenvalues of a graph ⋮ Complete characterization of graphs for direct comparing Zagreb indices ⋮ On a conjecture about the Randić index ⋮ On the extremal properties of the average eccentricity ⋮ Conjecture of TxGraffiti: Independence, domination, and matchings ⋮ Sharp bounds for the Randić index of graphs with given minimum and maximum degree ⋮ Old and new results on algebraic connectivity of graphs ⋮ The geometric-arithmetic index and the chromatic number of connected graphs ⋮ On mean distance and girth ⋮ Automated conjecturing. III. Property-relations conjectures ⋮ Design of highly synchronizable and robust networks ⋮ On the extremal cacti of given parameters with respect to the difference of Zagreb indices ⋮ Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited ⋮ Randić index and the diameter of a graph ⋮ Edge-grafting transformations on the average eccentricity of graphs and their applications ⋮ Proof of conjectures involving algebraic connectivity of graphs ⋮ A quadratic programming approach to the Randić index ⋮ Proof of the first part of the conjecture of Aouchiche and Hansen about the Randić index ⋮ Expected distance based on random walks ⋮ Upper bounds on the average eccentricity ⋮ The (revised) Szeged index and the Wiener index of a nonbipartite graph ⋮ On the relation between the positive inertia index and negative inertia index of weighted graphs ⋮ Using size for bounding expressions of graph invariants ⋮ Variable neighborhood search for extremal graphs. V: Three ways to automate finding conjectures ⋮ Some upper bounds related with domination number ⋮ Proofs of the AutoGraphiX conjectures on the domination number, average eccentricity and proximity ⋮ Extremal graphs of given parameters with respect to the eccentricity distance sum and the eccentric connectivity index ⋮ Proof of conjectures on remoteness and proximity in graphs ⋮ Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph ⋮ Nonsmooth optimization through mesh adaptive direct search and variable neighborhood search ⋮ Linear inequalities among graph invariants: Using GraPHedron to uncover optimal relationships ⋮ Corrections of proofs for Hansen and Mélot's two theorems ⋮ Metric properties of Sierpiński-like graphs ⋮ Tetracyclic graphs with extremal values of Randić index ⋮ Facet defining inequalities among graph invariants: The system graphedron ⋮ The Wiener index of Sierpiński-like graphs ⋮ Distance Laplacian eigenvalues and chromatic number in graphs ⋮ Minimum values of the second largest \(Q\)-eigenvalue ⋮ Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number ⋮ Distance spectra of graphs: a survey ⋮ Variable neighborhood search for extremal graphs 3 ⋮ On the spectral radius of graphs with a given domination number ⋮ A survey of automated conjectures in spectral graph theory ⋮ Bounds on the \(Q\)-spread of a graph ⋮ On the Zagreb index inequality of graphs with prescribed vertex degrees ⋮ On bags and bugs ⋮ Variable neighborhood search for extremal graphs. 22. Extending bounds for independence to upper irredundance ⋮ A sharp upper bound on algebraic connectivity using domination number ⋮ Bounds and conjectures for the signless Laplacian index of graphs ⋮ Variable neighbourhood search: methods and applications ⋮ Variable neighborhood search: Principles and applications ⋮ Relationship between the rank and the matching number of a graph ⋮ On the extremal values of the second largest \(Q\)-eigenvalue ⋮ Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph ⋮ Comparing Zagreb indices for connected graphs ⋮ On a relation between the Randić index and the chromatic number ⋮ On a conjecture about the Szeged index ⋮ Resolution of AutoGraphiX conjectures relating the index and matching number of graphs ⋮ On two conjectures of Randić index and the largest signless Laplacian eigenvalue of graphs ⋮ Recherche à voisinage variable de graphes extrémaux 13. à propos de la maille ⋮ The Randić index and the diameter of graphs ⋮ Nordhaus-Gaddum relations for proximity and remoteness in graphs ⋮ Average distance and maximum induced forest ⋮ Comment on ``complete solution to a conjecture on Randić index ⋮ Proximity, remoteness and girth in graphs ⋮ Relation between the skew-rank of an oriented graph and the independence number of its underlying graph ⋮ On the relationship between the skew-rank of an oriented graph and the rank of its underlying graph ⋮ Proofs of three conjectures on the quotients of the (revised) Szeged index and the Wiener index and beyond ⋮ On the distance signless Laplacian of a graph ⋮ On regular triangle-distinct graphs ⋮ Extremal graphs for the Randić index when minimum, maximum degrees and order of graphs are odd ⋮ On a conjecture of \textit{TxGraffiti}: relating zero forcing and vertex covers in graphs ⋮ On difference of Zagreb indices ⋮ Automated generation of conjectures on forbidden subgraph characterization ⋮ Minimal graphs with respect to the multiplicative version of some vertex-degree-based topological indices ⋮ Open problems on graph eigenvalues studied with AutoGraphiX ⋮ On the Laplacian coefficients of unicyclic graphs ⋮ On a conjecture of the Randić index ⋮ Recherche à voisinage variable de graphes extrémaux 26. Nouveaux résultats sur la maille ⋮ Comparing the Zagreb indices for graphs with small difference between the maximum and minimum degrees ⋮ Variable neighbourhood search: Methods and applications ⋮ GrInvIn in a nutshell ⋮ Proximity and remoteness in graphs: Results and conjectures ⋮ On the Zagreb indices equality ⋮ On the Randić index of graphs ⋮ Some properties of the distance Laplacian eigenvalues of a graph ⋮ Variable neighborhood search for extremal graphs. 23. On the Randić index and the chromatic number ⋮ Randić ordering of chemical trees ⋮ On the nullity number of graphs ⋮ Computers and discovery in algebraic graph theory ⋮ AutoGraphiX: a survey ⋮ The difference between remoteness and radius of a graph
Uses Software
This page was built for publication: Variable neighborhood search for extremal graphs. I: The AutoGraphiX system
