To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
Languages
Recent
Show all languages
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Core (graph theory)

From Wikipedia, the free encyclopedia

In the mathematical field of graph theory, a core is a notion that describes behavior of a graph with respect to graph homomorphisms.

YouTube Encyclopedic

  • 1/3
    Views:
    5 175
    1 795 153
    883
  • Graph Theory FAQs: 04. Isomorphism vs Homomorphism
  • Multiply Numbers And Algebra Equations By Drawing Lines
  • Core 1 - Curve Sketching 3 - Graph Transformations AS and A2 Maths Summer 2015

Transcription

Definition

Graph is a core if every homomorphism is an isomorphism, that is it is a bijection of vertices of .

A core of a graph is a graph such that

  1. There exists a homomorphism from to ,
  2. there exists a homomorphism from to , and
  3. is minimal with this property.

Two graphs are said to be homomorphism equivalent or hom-equivalent if they have isomorphic cores.

Examples

Properties

Every finite graph has a core, which is determined uniquely, up to isomorphism. The core of a graph G is always an induced subgraph of G. If and then the graphs and are necessarily homomorphically equivalent.

Computational complexity

It is NP-complete to test whether a graph has a homomorphism to a proper subgraph, and co-NP-complete to test whether a graph is its own core (i.e. whether no such homomorphism exists) (Hell & Nešetřil 1992).

References

  • Godsil, Chris, and Royle, Gordon. Algebraic Graph Theory. Graduate Texts in Mathematics, Vol. 207. Springer-Verlag, New York, 2001. Chapter 6 section 2.
  • Hell, Pavol; Nešetřil, Jaroslav (1992), "The core of a graph", Discrete Mathematics, 109 (1–3): 117–126, doi:10.1016/0012-365X(92)90282-K, MR 1192374.
  • Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Proposition 3.5", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 43, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
This page was last edited on 13 October 2022, at 10:41
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.