All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 11 Next

Displaying 201 – 220 of 255

Showing per page

Recherche à voisinage variable de graphes extrémaux 13. A propos de la maille

Mustapha Aouchiche, Pierre Hansen (2005)

RAIRO - Operations Research - Recherche Opérationnelle

Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d’autres fonctions, la génération automatique de conjectures en théorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afin d’illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjectures obtenues par ce système et de la forme b ̲ n ≤ g ⊕ i ≤ b ¯ n où g désigne la maille (ou longueur du plus petit cycle) du graphe G = ( V , E ) , i un autre invariant choisi parmi le nombre de stabilité,...

Recherche à voisinage variable de graphes extrémaux 13. à propos de la maille*

Mustapha Aouchiche, Pierre Hansen (2006)

RAIRO - Operations Research

Le système AutoGraphiX (AGX1 et AGX2) permet, parmi d'autres fonctions, la génération automatique de conjectures en théorie des graphes et, dans une version plus récente, la preuve automatique de conjectures simples. Afin d'illustrer ces fonctions et le type de résultats obtenus, nous étudions systématiquement ici des conjectures obtenues par ce système et de la forme b ̲ n ≤ g ⊕ i ≤ b ¯ n où g désigne la maille (ou longueur du plus petit cycle) du graphe G=(V, E), i un autre invariant choisi parmi le nombre...

Recursive generation of simple planar quadrangulations with vertices of degree 3 and 4

Mahdieh Hasheminezhad, Brendan D. McKay (2010)

Discussiones Mathematicae Graph Theory

We describe how the simple planar quadrangulations with vertices of degree 3 and 4, whose duals are known as octahedrites, can all be obtained from an elementary family of starting graphs by repeatedly applying two expansion operations. This allows for construction of a linear time generator of all graphs in the class with at most a given order, up to isomorphism.

Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic

Christian Laforest, Raksmey Phan (2013)

RAIRO - Operations Research - Recherche Opérationnelle

In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including...

Spanning trees with many or few colors in edge-colored graphs

Hajo Broersma, Xueliang Li (1997)

Discussiones Mathematicae Graph Theory

Given a graph G = (V,E) and a (not necessarily proper) edge-coloring of G, we consider the complexity of finding a spanning tree of G with as many different colors as possible, and of finding one with as few different colors as possible. We show that the first problem is equivalent to finding a common independent set of maximum cardinality in two matroids, implying that there is a polynomial algorithm. We use the minimum dominating set problem to show that the second problem is NP-hard.

Stable sets for ( P ₆ , K 2 , 3 ) -free graphs

Raffaele Mosca (2012)

Discussiones Mathematicae Graph Theory

The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for ( P ₆ , K 2 , 3 ) -free graphs in polynomial time, extending some known results.

Star Coloring of Subcubic Graphs

T. Karthick, C.R. Subramanian (2013)

Discussiones Mathematicae Graph Theory

A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time.

The Chromatic Number of Random Intersection Graphs

Katarzyna Rybarczyk (2017)

Discussiones Mathematicae Graph Theory

We study problems related to the chromatic number of a random intersection graph G (n,m, p). We introduce two new algorithms which colour G (n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G (n,m, p) asymptotically equals its clique number.

Currently displaying 201 – 220 of 255