For a connected graph whose 2-core contains a vertex of degree of a vertex at least three, suppress each maximal graph path with degree-two internal vertices to a single edge, allowing its two endpoints to coincide. Here suppression is the reverse of graph subdivision. The resulting multigraph, retaining self-loops and parallel edges, is its graph kernel. Each suppressed internal vertex removes one vertex and one edge, preserving graph excess; counting a self-loop twice toward degree of a vertex, every remaining vertex has degree of a vertex at least three. A purely cyclic 2-core is a separate unicyclic case: it has no branching vertex to anchor this construction.
For the barbell in bridges and connectivity in the 2-core, the graph kernel has two vertices , one self-loop at each, and a single joining edge . Suppressing contracts the joining graph path to that bridge in a graph; suppressing the two other vertices on each triangle turns the triangle into a self-loop. The graph excess stays . Thus forming a graph kernel compresses degree-two chains rather than deleting everything outside graph cycles.
A graph kernel is a method used in machine learning and pattern recognition that measures the similarity between two graphs. Graphs are data structures composed of nodes (or vertices) and edges connecting these nodes. They can represent various types of data, such as social networks, molecular structures, and more. Graph kernels are particularly useful for tasks involving graph-structured data, where traditional vector-based methods are not applicable.
New to topics? Read the docs here!