Publication

On the power of combinatorial and spectral invariants

2010
Conference Papers

Abstract

We extend the traditional spectral invariants (spectrum and angles) by a stronger polynomial time computable graph invariant based on the angles between projections of standard basis vectors into the eigenspaces (in addition to the usual angles between standard basis vectors and eigenspaces). The exact power of the new invariant is still an open problem. We also define combinatorial invariants based on standard graph isomorphism heuristics and compare their strengths with the spectral invariants. In particular, we show that a simple edge coloring invariant is at least as powerful as all these spectral invariants. (C) 2009 Elsevier Inc. All rights reserved.

Official source

https://infoscience.epfl.ch/entities/publication/4bd4434c-4673-46bf-9f87-b1a531edaf9d

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

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.

2010
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/4bd4434c-4673-46bf-9f87-b1a531edaf9d

About this result

Related concepts (32)

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Matroid

In combinatorics, a branch of mathematics, a matroid ˈmeɪtrɔɪd is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being in terms of: independent sets; bases or circuits; rank functions; closure operators; and closed sets or flats. In the language of partially ordered sets, a finite simple matroid is equivalent to a geometric lattice.

Standard basis

In mathematics, the standard basis (also called natural basis or canonical basis) of a coordinate vector space (such as or ) is the set of vectors, each of whose components are all zero, except one that equals 1. For example, in the case of the Euclidean plane formed by the pairs (x, y) of real numbers, the standard basis is formed by the vectors Similarly, the standard basis for the three-dimensional space is formed by vectors Here the vector ex points in the x direction, the vector ey points in the y direction, and the vector ez points in the z direction.