Apex graph | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

In graph theory, a branch of mathematics, an apex graph is a graph that can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph. It is an apex, not the apex because an apex graph may have more than one apex; for example, in the minimal nonplanar graphs K_5 or K_3,3, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove. Apex graphs are closed under the operation of taking minors and play a role in several other aspects of graph minor theory: linkless embedding, Hadwiger's conjecture, YΔY-reducible graphs, and relations between treewidth and graph diameter. Apex graphs are closed under the operation of taking minors: contracting any edge, or removing any edge or vertex, leads to another apex graph. For, if G is an apex graph with apex v, then any contraction or removal that does not involve v preserves the planarity of the remaining graph, as does any edge removal of an edge incident to v. If an edge incident to v is contracted, the effect on the remaining graph is equivalent to the removal of the other endpoint of the edge. And if v itself is removed, any other vertex may be chosen as the apex. By the Robertson–Seymour theorem, because they form a minor-closed family of graphs, the apex graphs have a forbidden graph characterization. There are only finitely many graphs that are neither apex graphs nor have another non-apex graph as a minor. These graphs are forbidden minors for the property of being an apex graph. Any other graph G is an apex graph if and only if none of the forbidden minors is a minor of G. These forbidden minors include the seven graphs of the Petersen family, three disconnected graphs formed from the disjoint unions of two of K_5 and K_3,3, and many other graphs. However, a complete description of them remains unknown.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (20)

Séances de cours associées (2)

Pathwidth

In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number that measures how much the path was thickened to form G. More formally, a path-decomposition is a sequence of subsets of vertices of G such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets, and the pathwidth is one less than the size of the largest set in such a decomposition.

Apex graph

Famille de Petersen

thumb|300px|La famille de Petersen. Le graphe complet K6 est en haut de l'illustration, et le graphe de Petersen est en bas. Les liaisons bleues indiquent des transformations Δ-Y ou Y-Δ entre les graphe s de la famille. En mathématiques, et plus précisément en théorie des graphes, la famille de Petersen est un ensemble de sept graphes non orientés contenant le graphe de Petersen et le graphe complet K6. Cette famille a été découverte et étudiée par le mathématicien danois Julius Petersen.

Algorithme de Stein : Test d'identité polynomiale CS-450: Algorithms II

Explore l'algorithme Stein pour le test d'identité polynomiale et la minimisation d'un problème de coupe.

Chimie organique : groupes fonctionnels et structure moléculaire CH-110: Advanced general chemistry I

Explore les réactions acido-basiques, les groupes fonctionnels, l'électronégativité et la résonance en chimie organique.