Publication

The struction of a graph: Application toCN-free graphs

Dominique de Werra
1985

Abstract

We consider the class of graphs characterized by the forbidden subgraphsC andN:C is the claw (unique graph with degree sequence (3, 1, 1, 1)) andN the net (unique graph with degree sequence (3, 3, 3, 1, 1, 1)). For this class of graphs (calledCN-free) an algorithm is described for determining the stability numberα(G). It is based on a construction associating with anyCN-free graphG anotherCN-free graphG′ such thatα(G′)=α(G)−1. Such a construction reducing the stability number is called a struction.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Dominique de Werra
1985

Abstract

Official source

Related concepts (25)

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

Dual graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e.

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

Related publications (9)

The struction of a graph: Application toCN-free graphs

Chat with Graph Search

Parallel framework for intelligent prediction of multi-site fugitive dust: Combined with DustLSTM-Trans and FedProx-Dyn

A Framework for Efficient Estimation of Closeness Centrality and Eccentricity in Large Networks

Spherical Convolutionnal Neural Networks: Empirical Analysis of SCNNs