Displaying similar documents to “Partial covers of graphs”

Distinguishing graphs by the number of homomorphisms

Steve Fisk (1995)

Discussiones Mathematicae Graph Theory

Similarity:

A homomorphism from one graph to another is a map that sends vertices to vertices and edges to edges. We denote the number of homomorphisms from G to H by |G → H|. If 𝓕 is a collection of graphs, we say that 𝓕 distinguishes graphs G and H if there is some member X of 𝓕 such that |G → X | ≠ |H → X|. 𝓕 is a distinguishing family if it distinguishes all pairs of graphs. We show that various collections of graphs are a distinguishing family.

The Thickness of Amalgamations and Cartesian Product of Graphs

Yan Yang, Yichao Chen (2017)

Discussiones Mathematicae Graph Theory

Similarity:

The thickness of a graph is the minimum number of planar spanning subgraphs into which the graph can be decomposed. It is a measurement of the closeness to the planarity of a graph, and it also has important applications to VLSI design, but it has been known for only few graphs. We obtain the thickness of vertex-amalgamation and bar-amalgamation of graphs, the lower and upper bounds for the thickness of edge-amalgamation and 2-vertex-amalgamation of graphs, respectively. We also study...

Supermagic Generalized Double Graphs 1

Jaroslav Ivančo (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is called supermagic if it admits a labelling of the edges by pairwise di erent consecutive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In this paper we will introduce some constructions of supermagic labellings of some graphs generalizing double graphs. Inter alia we show that the double graphs of regular Hamiltonian graphs and some circulant graphs are supermagic.

Heuristic and metaheuristic methods for computing graph treewidth

François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2010)

RAIRO - Operations Research

Similarity:

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still...