{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/71218"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/71218","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Polynomials of the Adjacency Matrix of a Graph (distance-Transitive, Distance-Regular, Orbit)","abstract":"Given graphs (GAMMA) and (DELTA), and a real polynomial r(x), we will say that (DELTA) is generated from (GAMMA) by r(x) if r(A((GAMMA))) = A((DELTA)) where A((GAMMA)) and A((DELTA)) are adjacency matrices. For several interesting classes of graphs it is possible to determine all of the graphs which can be generated by a polynomial. Define the ith distance graph, (GAMMA)(,i), as the graph with the same vertex set as (GAMMA) and two vertices are adjacent in (GAMMA)(,i) if and only if they are a distance i apart. If (GAMMA) is a distance-regular graph, then for each i there exists a polynomial of degree i, p(,i)(x), such that p(,i)(A((GAMMA))) = A((GAMMA)(,i)). In fact, it has been shown that this property characterizes distance-regular graphs.","abstract_html":"Given graphs (GAMMA) and (DELTA), and a real polynomial r(x), we will say that (DELTA) is generated from (GAMMA) by r(x) if r(A((GAMMA))) = A((DELTA)) where A((GAMMA)) and A((DELTA)) are adjacency matrices. For several interesting classes of graphs it is possible to determine all of the graphs which can be generated by a polynomial. Define the ith distance graph, (GAMMA)(,i), as the graph with the same vertex set as (GAMMA) and two vertices are adjacent in (GAMMA)(,i) if and only if they are a distance i apart. If (GAMMA) is a distance-regular graph, then for each i there exists a polynomial of degree i, p(,i)(x), such that p(,i)(A((GAMMA))) = A((GAMMA)(,i)). In fact, it has been shown that this property characterizes distance-regular graphs.","abstract_has_math":false,"creators":["Beezer, Robert Arnold"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-16T06:18:09Z","date_published":"2014-12-16T06:18:09Z","updated_at":"2026-07-22T22:26:04Z","subjects":["Mathematics"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8422017"],"render_values":[{"text":"(UMI)AAI8422017","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/71218","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Beezer, Robert Arnold"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-16T06:18:09Z","10000-01-01","1984"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Mathematics"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/71218","(UMI)AAI8422017"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Given graphs (GAMMA) and (DELTA), and a real polynomial r(x), we will say that (DELTA) is generated from (GAMMA) by r(x) if r(A((GAMMA))) = A((DELTA)) where A((GAMMA)) and A((DELTA)) are adjacency matrices. For several interesting classes of graphs it is possible to determine all of the graphs which can be generated by a polynomial. Define the ith distance graph, (GAMMA)(,i), as the graph with the same vertex set as (GAMMA) and two vertices are adjacent in (GAMMA)(,i) if and only if they are a distance i apart. If (GAMMA) is a distance-regular graph, then for each i there exists a polynomial of degree i, p(,i)(x), such that p(,i)(A((GAMMA))) = A((GAMMA)(,i)). In fact, it has been shown that this property characterizes distance-regular graphs.","With the above situation in mind, we construct the definition of an orbit polynomial graph. A graph is orbit polynomial if certain natural 0-1 matrices (determined by the automorphism group of the graph) are equal to polynomials of the adjacency matrix of the graph. We obtain many results about the properties of these graphs and their connections with association schemes. We also characterize orbit polynomial graphs with a prime number of vertices and the non-symmetric trivalent orbit polynomial graphs.","We then study the graphs generated from a tree by a polynomial. For a path, all of the possible graphs are determined. A sunset is a path of even length with additional vertices adjacent to the central vertex. We produce a polynomial q(x) which generates a graph from a sunset which happens to be isomorphic to the original sunset. Motivated by this example, we study the situation where r(A((GAMMA))) = A((DELTA)), r(x) (NOT=) x, and (GAMMA) is isomorphic to (DELTA).","Made available in DSpace on 2014-12-16T06:18:09Z (GMT). No. of bitstreams: 1 8422017.pdf: 2733092 bytes, checksum: cf35accee1f57e2961063fda816bc68d (MD5) Previous issue date: 1984","Embargo set by: Seth Robbins for item 71384 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","112 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984."]},{"key":"dc:title","label":"Title","values":["Polynomials of the Adjacency Matrix of a Graph (distance-Transitive, Distance-Regular, Orbit)"]}]}],"canonical_facts":{"dc:creator":["Beezer, Robert Arnold"],"dc:date":["2014-12-16T06:18:09Z","10000-01-01","1984"],"dc:description":["Given graphs (GAMMA) and (DELTA), and a real polynomial r(x), we will say that (DELTA) is generated from (GAMMA) by r(x) if r(A((GAMMA))) = A((DELTA)) where A((GAMMA)) and A((DELTA)) are adjacency matrices. For several interesting classes of graphs it is possible to determine all of the graphs which can be generated by a polynomial. Define the ith distance graph, (GAMMA)(,i), as the graph with the same vertex set as (GAMMA) and two vertices are adjacent in (GAMMA)(,i) if and only if they are a distance i apart. If (GAMMA) is a distance-regular graph, then for each i there exists a polynomial of degree i, p(,i)(x), such that p(,i)(A((GAMMA))) = A((GAMMA)(,i)). In fact, it has been shown that this property characterizes distance-regular graphs.","With the above situation in mind, we construct the definition of an orbit polynomial graph. A graph is orbit polynomial if certain natural 0-1 matrices (determined by the automorphism group of the graph) are equal to polynomials of the adjacency matrix of the graph. We obtain many results about the properties of these graphs and their connections with association schemes. We also characterize orbit polynomial graphs with a prime number of vertices and the non-symmetric trivalent orbit polynomial graphs.","We then study the graphs generated from a tree by a polynomial. For a path, all of the possible graphs are determined. A sunset is a path of even length with additional vertices adjacent to the central vertex. We produce a polynomial q(x) which generates a graph from a sunset which happens to be isomorphic to the original sunset. Motivated by this example, we study the situation where r(A((GAMMA))) = A((DELTA)), r(x) (NOT=) x, and (GAMMA) is isomorphic to (DELTA).","Made available in DSpace on 2014-12-16T06:18:09Z (GMT). No. of bitstreams: 1 8422017.pdf: 2733092 bytes, checksum: cf35accee1f57e2961063fda816bc68d (MD5) Previous issue date: 1984","Embargo set by: Seth Robbins for item 71384 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","112 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1984."],"dc:identifier":["http://hdl.handle.net/2142/71218","(UMI)AAI8422017"],"dc:subject":["Mathematics"],"dc:title":["Polynomials of the Adjacency Matrix of a Graph (distance-Transitive, Distance-Regular, Orbit)"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:04Z"}