An Introduction to Coding Sequences of Graphs

DOI10.1007/978-3-319-48749-6_15zbMATH Open1486.05208arXiv1505.04602OpenAlexW2281290671MaRDI QIDQ2958314

Author name not available (Why is that?)

Publication date: 1 February 2017

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Abstract: In his pioneering paper on matroids in 1935, Whitney obtained a characterization for binary matroids and left a comment at end of the paper that the problem of characterizing graphic matroids is the same as that of characterizing matroids which correspond to matrices (mod 2) with exactly two ones in each column. Later on Tutte obtained a characterization of graphic matroids in terms of forbidden minors in 1959. It is clear that Whitney indicated about incidence matrices of simple undirected graphs. Here we introduce the concept of a segment binary matroid which corresponds to matrices over $mathbb{Z}_2$ which has the consecutive $1$'s property (i.e., $1$'s are consecutive) for columns and obtained a characterization of graphic matroids in terms of this. In fact, we introduce a new representation of simple undirected graphs in terms of some vectors of finite dimensional vector spaces over $mathbb{Z}_2$ which satisfy consecutive $1$'s property. The set of such vectors is called a coding sequence of a graph $G$. Among all such coding sequences we identify the one which is unique for a class of isomorphic graphs. We call it the code of the graph. We characterize several classes of graphs in terms of coding sequences. It is shown that a graph $G$ with $n$ vertices is a tree if and only if any coding sequence of $G$ is a basis of the vector space $mathbb{Z}_2^{n-1}$ over $mathbb{Z}_2$. Moreover considering coding sequences as binary matroids, we obtain a characterization for simple graphic matroids and found a necessary and sufficient condition for graph isomorphism in terms of a special matroid isomorphism between their corresponding coding sequences. For this, we introduce the concept of strong isomorphisms of segment binary matroids and show that two simple (undirected) graphs are isomorphic if and only if their canonical sequences are strongly isomorphic segment binary matroids.

Full work available at URL: https://arxiv.org/abs/1505.04602

zbMATH Keywords

incidence matrixbinary matroidgraphic matroidgraph isomorphismgraph representationconsecutive ones propertysimple undirected graph

Mathematics Subject Classification ID

Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matroids and Graphs
• Graphs and Vector Spaces
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• On the Abstract Properties of Linear Dependence
• On Vector Spaces Associated with a Graph

Recommendations

• Title not available (Why is that?) 👍 👎
• On graphs and codes 👍 👎
• On the coding of ordered graphs 👍 👎
• An application of coding theory to a problem in graphical enumeration 👍 👎
• Graph Theoretic Methods in Coding Theory 👍 👎
• Codes on Graphs: Fundamentals 👍 👎
• A graph theoretic encoding of Lucas sequences 👍 👎
• CODING IN GRAPHS AND LINEAR ORDERINGS 👍 👎
• Structured Codes of Graphs 👍 👎
• Codes on graphs: Recent progress 👍 👎

This page was built for publication: An Introduction to Coding Sequences of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2958314)