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 Nc47adb4bdfb7476d83b2d05f8eacdc80
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 N620689d9ea9042e793ca12452f9e8088
11 N9b46e308c66a48cf820a06c31cab918c
12 sg:journal.1136750
13 schema:name A New Adjacency Matrix for Finite Graphs
14 schema:pagination 979-991
15 schema:productId N53111ce459564fdf8579658fadbe4b00
16 N76d2986f9ff14905aa81f76a2e7e3806
17 Nfbf46d4fc8574843b5cbea919ba6f490
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 N0443b3a24a97435f84f532482105c540
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 N0443b3a24a97435f84f532482105c540 schema:name Springer Nature - SN SciGraph project
28 rdf:type schema:Organization
29 N53111ce459564fdf8579658fadbe4b00 schema:name dimensions_id
30 schema:value pub.1027228484
31 rdf:type schema:PropertyValue
32 N620689d9ea9042e793ca12452f9e8088 schema:issueNumber 3-4
33 rdf:type schema:PublicationIssue
34 N76d2986f9ff14905aa81f76a2e7e3806 schema:name doi
35 schema:value 10.1007/s00006-008-0116-5
36 rdf:type schema:PropertyValue
37 N9b46e308c66a48cf820a06c31cab918c schema:volumeNumber 18
38 rdf:type schema:PublicationVolume
39 Nc47adb4bdfb7476d83b2d05f8eacdc80 rdf:first sg:person.013015301341.40
40 rdf:rest rdf:nil
41 Nfbf46d4fc8574843b5cbea919ba6f490 schema:name readcube_id
42 schema:value 81b4b4a3be06b809297fb8783e3cd703f978ee829f71727702ff29f143d4d392
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)


...