A characterization of graphs by codes from their incidence matrices

MaRDI QIDQ396825zbMATH OpenFDO

Authors Peter Dankelmann, B. G. Rodrigues, J. D. Key

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p18

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

connected graphsedge-connectivityincidence matrixlinear codes

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Linear codes (general theory) (94B05)

Review text

Summary: We continue our earlier investigation of properties of linear codes generated by the rows of incidence matrices of \(k\)-regular connected graphs on \(n\) vertices. The notion of edge connectivity is used to show that, for a wide range of such graphs, the \(p\)-ary code, for all primes \(p\), from an \(n \times \frac{1}{2}nk\) incidence matrix has dimension \(n\) or \(n-1\), minimum weight \(k\), the minimum words are the scalar multiples of the rows, there is a gap in the weight enumerator between \(k\) and \(2k-2\), and the words of weight \(2k-2\) are the scalar multiples of the differences of intersecting rows of the matrix. For such graphs, the graph can thus be retrieved from the code.

Recommendations

• Codes from incidence matrices of graphs
• Codes from incidence matrices of some regular graphs
• Codes from the incidence matrices and line graphs of Hamming graphs H^k(n,2) for k 2
• Hulls of codes from incidence matrices of connected regular graphs
• Binary codes of strongly regular graphs

Cites work

• Asymptotic Formulas for the Probability of k-Connectedness of Random Graphs
• Bipartite graphs and digraphs with maximum connectivity
• Codes associated with triangular graphs and permutation decoding
• Codes from adjacency matrices of uniform subset graphs
• Codes from incidence matrices and line graphs of Hamming graphs
• Codes from incidence matrices and line graphs of Paley graphs
• Codes from incidence matrices of graphs
• Codes from lattice and related graphs, and permutation decoding
• Codes from the incidence matrices and line graphs of Hamming graphs H^k(n,2) for k 2
• Diameter-sufficient conditions for a graph to be super-restricted connected
• Eigenvalues and perfect matchings
• Graph theoretic error-correcting codes
• scientific article; zbMATH DE number 3735859 (Why is no real title available?)
• scientific article; zbMATH DE number 53917 (Why is no real title available?)
• Minimum words of codes from affine planes
• Neighborhood conditions for graphs to be super restricted edge connected
• On super 2-restricted and 3-restricted edge-connected vertex transitive graphs
• On super restricted edge connectivity of half vertex transitive graphs
• On super restricted edge-connectivity of edge-transitive graphs
• On super-edge-connected digraphs and bipartite digraphs
• Radius, diameter, and minimum degree
• Sufficient conditions for bipartite graphs to be super-\(k\)-restricted edge connected
• Sufficient conditions for graphs to be ??-optimal, super-edge-connected, and maximally edge-connected
• Sufficient conditions for triangle-free graphs to be optimally restricted edge-connected
• Super restricted edge connectivity of regular edge-transitive graphs
• Super restricted edge connectivity of regular graphs
• Super restricted edge-connectivity of vertex-transitive graphs
• Superconnectivity of bipartite digraphs and graphs
• The Magma algebra system. I: The user language

Cited in

(21)

• PD-sets for the codes from incidence matrices of triangular graphs
• Codes from incidence matrices of graphs
• On the number of minimal codewords in codes generated by the adjacency matrix of a graph
• Ternary codes from some reflexive uniform subset graphs
• Codes from the incidence matrices and line graphs of Hamming graphs H^k(n,2) for k 2
• Binary codes from Paley graphs of prime-power-square order
• Binary codes from reflexive uniform subset graphs on 3-sets
• Codes from neighbourhood designs of the graphs \(\text{GP}(q,\frac{q-1}{2})\) with \(q\) odd
• Hulls of codes from incidence matrices of connected regular graphs
• Codes associated with the odd graphs
• scientific article; zbMATH DE number 9818 (Why is no real title available?)
• Graph theoretic aspects of minimum distance and equivalence of binary linear codes
• Codes from incidence matrices of some Bouwer graphs
• Vertex codes of graphs
• scientific article; zbMATH DE number 975362 (Why is no real title available?)
• Isodual and self-dual codes from graphs
• The weight distribution of hulls of binary codes from incidence matrices of complete graphs
• On some codes from rank 3 primitive actions of the simple Chevalley group G₂(q)
• Connectivity graph-codes
• Designer of codes: a tribute to Jennifer Key
• Codes from incidence matrices of hypergraphs

Describes a project that uses

Uses Software

• Magma

This page was built for publication: A characterization of graphs by codes from their incidence matrices

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