A New Adjacency Matrix for Finite Graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2008-09

AUTHORS

George Stacey Staples

ABSTRACT

This paper expands on the graph-theoretic content of my contributed talk at the Seventh International Conference on Clifford Algebras and Their Applications. A well-known result in graph theory states that when A is the adjacency matrix of a finite graph G, the entries of Ak represent numbers of k-step walks existing in G. However, the adjacency matrix fails to distinguish between walks and “self-avoiding” walks (i.e., walks without repeated vertices). Utilizing elements of abelian, nilpotent-generated algebras, a “new” adjacency matrix is associated with a finite graph on n vertices. By considering entries of , where is an appropriate nilpotent adjacency matrix, one is able to recover the self-avoiding k-walks in any finite graph. In particular, a graph’s Hamiltonian cycles are enumerated by the top-form coefficient in the trace of when n is the number of vertices in the graph. By considering the ℓth power of the trace of , ℓ-tuples of pairwise-disjoint k-cycles are recovered. By defining a nilpotent transition matrix associated with a time-homogeneous Markov chain, a method of computing probabilities of self-avoiding random walks on finite graphs is developed. Expected hitting times of specific states in Markov chains and expected times of first self-intersection of random walks are also recovered using these methods. The algebra used to define the nilpotent adjacency matrix of a graph on n vertices is not itself a Clifford algebra, but it can be constructed within the 2n-particle fermion algebra , indicating potential connections to quantum computing. More... »

PAGES

979-991

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00006-008-0116-5

DOI

http://dx.doi.org/10.1007/s00006-008-0116-5

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1027228484


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Southern Illinois University Edwardsville", 
          "id": "https://www.grid.ac/institutes/grid.263857.d", 
          "name": [
            "Department of Mathematics and Statistics, Southern Illinois University at Edwardsville, Box 1653, Edwardsville62026-1653, Illinois, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Staples", 
        "givenName": "George Stacey", 
        "id": "sg:person.013015301341.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013015301341.40"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2008-09", 
    "datePublishedReg": "2008-09-01", 
    "description": "This paper expands on the graph-theoretic content of my contributed talk at the Seventh International Conference on Clifford Algebras and Their Applications. A well-known result in graph theory states that when A is the adjacency matrix of a finite graph G, the entries of Ak represent numbers of k-step walks existing in G. However, the adjacency matrix fails to distinguish between walks and \u201cself-avoiding\u201d walks (i.e., walks without repeated vertices). Utilizing elements of abelian, nilpotent-generated algebras, a \u201cnew\u201d adjacency matrix is associated with a finite graph on n vertices. By considering entries of , where is an appropriate nilpotent adjacency matrix, one is able to recover the self-avoiding k-walks in any finite graph. In particular, a graph\u2019s Hamiltonian cycles are enumerated by the top-form coefficient in the trace of when n is the number of vertices in the graph. By considering the \u2113th power of the trace of , \u2113-tuples of pairwise-disjoint k-cycles are recovered. By defining a nilpotent transition matrix associated with a time-homogeneous Markov chain, a method of computing probabilities of self-avoiding random walks on finite graphs is developed. Expected hitting times of specific states in Markov chains and expected times of first self-intersection of random walks are also recovered using these methods. The algebra used to define the nilpotent adjacency matrix of a graph on n vertices is not itself a Clifford algebra, but it can be constructed within the 2n-particle fermion algebra , indicating potential connections to quantum computing.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00006-008-0116-5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136750", 
        "issn": [
          "0188-7009", 
          "1661-4909"
        ], 
        "name": "Advances in Applied Clifford Algebras", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3-4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "18"
      }
    ], 
    "name": "A New Adjacency Matrix for Finite Graphs", 
    "pagination": "979-991", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "81b4b4a3be06b809297fb8783e3cd703f978ee829f71727702ff29f143d4d392"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00006-008-0116-5"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1027228484"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00006-008-0116-5", 
      "https://app.dimensions.ai/details/publication/pub.1027228484"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T10:21", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000348_0000000348/records_54336_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00006-008-0116-5"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00006-008-0116-5'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00006-008-0116-5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00006-008-0116-5'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00006-008-0116-5'


 

This table displays all metadata directly associated to this object as RDF triples.

61 TRIPLES      20 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00006-008-0116-5 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nb32373251b73460582855f7a5cb9a0e0
4 schema:datePublished 2008-09
5 schema:datePublishedReg 2008-09-01
6 schema:description This paper expands on the graph-theoretic content of my contributed talk at the Seventh International Conference on Clifford Algebras and Their Applications. A well-known result in graph theory states that when A is the adjacency matrix of a finite graph G, the entries of Ak represent numbers of k-step walks existing in G. However, the adjacency matrix fails to distinguish between walks and “self-avoiding” walks (i.e., walks without repeated vertices). Utilizing elements of abelian, nilpotent-generated algebras, a “new” adjacency matrix is associated with a finite graph on n vertices. By considering entries of , where is an appropriate nilpotent adjacency matrix, one is able to recover the self-avoiding k-walks in any finite graph. In particular, a graph’s Hamiltonian cycles are enumerated by the top-form coefficient in the trace of when n is the number of vertices in the graph. By considering the ℓth power of the trace of , ℓ-tuples of pairwise-disjoint k-cycles are recovered. By defining a nilpotent transition matrix associated with a time-homogeneous Markov chain, a method of computing probabilities of self-avoiding random walks on finite graphs is developed. Expected hitting times of specific states in Markov chains and expected times of first self-intersection of random walks are also recovered using these methods. The algebra used to define the nilpotent adjacency matrix of a graph on n vertices is not itself a Clifford algebra, but it can be constructed within the 2n-particle fermion algebra , indicating potential connections to quantum computing.
7 schema:genre research_article
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N75fd626db3c14329993afbe819e4837c
11 Nf30f1694b04c40f48f7dbb037884ec98
12 sg:journal.1136750
13 schema:name A New Adjacency Matrix for Finite Graphs
14 schema:pagination 979-991
15 schema:productId Nb20947695de046bb914ceae988430cd4
16 Ne941d6a544054ce0b14b67a11997e015
17 Nfb114e42b5fa4d33ab26a7b06a3e38ab
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027228484
19 https://doi.org/10.1007/s00006-008-0116-5
20 schema:sdDatePublished 2019-04-11T10:21
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Na8f0e7238e80498fbb57a8f77a721d56
23 schema:url https://link.springer.com/10.1007%2Fs00006-008-0116-5
24 sgo:license sg:explorer/license/
25 sgo:sdDataset articles
26 rdf:type schema:ScholarlyArticle
27 N75fd626db3c14329993afbe819e4837c schema:issueNumber 3-4
28 rdf:type schema:PublicationIssue
29 Na8f0e7238e80498fbb57a8f77a721d56 schema:name Springer Nature - SN SciGraph project
30 rdf:type schema:Organization
31 Nb20947695de046bb914ceae988430cd4 schema:name readcube_id
32 schema:value 81b4b4a3be06b809297fb8783e3cd703f978ee829f71727702ff29f143d4d392
33 rdf:type schema:PropertyValue
34 Nb32373251b73460582855f7a5cb9a0e0 rdf:first sg:person.013015301341.40
35 rdf:rest rdf:nil
36 Ne941d6a544054ce0b14b67a11997e015 schema:name dimensions_id
37 schema:value pub.1027228484
38 rdf:type schema:PropertyValue
39 Nf30f1694b04c40f48f7dbb037884ec98 schema:volumeNumber 18
40 rdf:type schema:PublicationVolume
41 Nfb114e42b5fa4d33ab26a7b06a3e38ab schema:name doi
42 schema:value 10.1007/s00006-008-0116-5
43 rdf:type schema:PropertyValue
44 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
45 schema:name Mathematical Sciences
46 rdf:type schema:DefinedTerm
47 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
48 schema:name Pure Mathematics
49 rdf:type schema:DefinedTerm
50 sg:journal.1136750 schema:issn 0188-7009
51 1661-4909
52 schema:name Advances in Applied Clifford Algebras
53 rdf:type schema:Periodical
54 sg:person.013015301341.40 schema:affiliation https://www.grid.ac/institutes/grid.263857.d
55 schema:familyName Staples
56 schema:givenName George Stacey
57 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013015301341.40
58 rdf:type schema:Person
59 https://www.grid.ac/institutes/grid.263857.d schema:alternateName Southern Illinois University Edwardsville
60 schema:name Department of Mathematics and Statistics, Southern Illinois University at Edwardsville, Box 1653, Edwardsville62026-1653, Illinois, USA
61 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...