Core (graph theory)

<h2 id="definition">Definition</h2>
<p>Graph 
  
    
      
        C
      
    
    {\displaystyle C}
  
 is a core if every homomorphism 
  
    
      
        f
        :
        C
        →
        C
      
    
    {\displaystyle f:C\to C}
  
 is an <a href="/facts/Graph_isomorphism/SBjVIhwW">isomorphism</a>, that is it is a bijection of vertices of 
  
    
      
        C
      
    
    {\displaystyle C}
  
.
</p><p>A core of a graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is a graph 
  
    
      
        C
      
    
    {\displaystyle C}
  
 such that
</p>
<ol><li>There exists a homomorphism from 
  
    
      
        G
      
    
    {\displaystyle G}
  
 to 
  
    
      
        C
      
    
    {\displaystyle C}
  
,</li>
<li>there exists a homomorphism from 
  
    
      
        C
      
    
    {\displaystyle C}
  
 to 
  
    
      
        G
      
    
    {\displaystyle G}
  
, and</li>
<li>
  
    
      
        C
      
    
    {\displaystyle C}
  
 is minimal with this property.</li></ol>
<p>Two graphs are said to be homomorphism equivalent or hom-equivalent if they have isomorphic cores.
</p>
<h2 id="examples">Examples</h2>
<ul><li>Any <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> is a core.</li>
<li>A <a href="/facts/Cycle_(graph_theory)/Is44edrv">cycle</a> of odd length is a core.</li>
<li>A graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is a core if and only if the core of 
  
    
      
        G
      
    
    {\displaystyle G}
  
 is equal to 
  
    
      
        G
      
    
    {\displaystyle G}
  
.</li>
<li>Every two cycles of even length, and more generally every two <a href="/facts/Bipartite_graph/xWcXV9MB">bipartite graphs</a> are hom-equivalent. The core of each of these graphs is the two-vertex complete graph <i>K</i>2.</li>
<li>By the <a href="/facts/Beckman%E2%80%93Quarles_theorem/3fDc8v97">Beckman–Quarles theorem</a>, the infinite <a href="/facts/Unit_distance_graph/8y4Ctq53">unit distance graph</a> on all points of the <a href="/facts/Euclidean_plane/tAUtRFcn">Euclidean plane</a> or of any higher-dimensional <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a> is a core.</li></ul>
<h2 id="properties">Properties</h2>
<p>Every finite graph has a core, which is determined uniquely, up to <a href="/facts/Graph_isomorphism/SBjVIhwW">isomorphism</a>. The core of a graph <i>G</i> is always an <a href="/facts/Induced_subgraph/G3EUC0MQ">induced subgraph</a> of <i>G</i>. If 
  
    
      
        G
        →
        H
      
    
    {\displaystyle G\to H}
  
 and 
  
    
      
        H
        →
        G
      
    
    {\displaystyle H\to G}
  
 then the graphs 
  
    
      
        G
      
    
    {\displaystyle G}
  
 and 
  
    
      
        H
      
    
    {\displaystyle H}
  
 are necessarily <a href="/facts/Homomorphic_equivalence/t8THAXCg">homomorphically equivalent</a>.
</p>
<h2 id="computational-complexity">Computational complexity</h2>
<p>It is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> 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).
</p>

<ul><li><a href="/facts/Chris_Godsil/ygA2pwGf">Godsil, Chris</a>, and <a href="/facts/Gordon_Royle/D5QQ6qkt">Royle, Gordon</a>.  <i>Algebraic Graph Theory.</i>  Graduate Texts in Mathematics, Vol. 207.  Springer-Verlag, New York, 2001.  Chapter 6 section 2.</li>
<li><a href="/facts/Pavol_Hell/qjFVH22X">Hell, Pavol</a>; <a href="/facts/Jaroslav_Ne%C5%A1et%C5%99il/99pR0wFP">Nešetřil, Jaroslav</a> (1992), "The core of a graph", <i><a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a></i>, 109 (1–3): 117–126, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2892%2990282-K">10.1016/0012-365X(92)90282-K</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1192374">1192374</a>.</li>
<li><a href="/facts/Jaroslav_Ne%C5%A1et%C5%99il/99pR0wFP">Nešetřil, Jaroslav</a>; <a href="/facts/Patrice_Ossona_de_Mendez/UdmKUVR7">Ossona de Mendez, Patrice</a> (2012), "Proposition 3.5", <i>Sparsity: Graphs, Structures, and Algorithms</i>, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 43, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-642-27875-4">10.1007/978-3-642-27875-4</a>, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-642-27874-7, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2920058">2920058</a>.</li></ul>

Core (graph theory) open-in-new

Core (graph theory)