{"id":12844,"date":"2021-11-22T18:32:02","date_gmt":"2021-11-22T23:32:02","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12844"},"modified":"2026-06-02T14:59:25","modified_gmt":"2026-06-02T18:59:25","slug":"tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/","title":{"rendered":"TR-96-14: Symmetries and Sense of Direction in Labeled Graphs"},"content":{"rendered":"\n<section class=\"w-screen px-6 cu-section cu-section--white ml-offset-center md:px-8 lg:px-14\">\n    <div class=\"space-y-6 cu-max-w-child-5xl  md:space-y-10 cu-prose-first-last\">\n\n            <div class=\"cu-textmedia flex flex-col lg:flex-row mx-auto gap-6 md:gap-10 my-6 md:my-12 first:mt-0 max-w-5xl\">\n        <div class=\"justify-start cu-textmedia-content cu-prose-first-last\" style=\"flex: 0 0 100%;\">\n            <header class=\"font-light prose-xl cu-pageheader md:prose-2xl cu-component-updated cu-prose-first-last\">\n                                    <h1 class=\"cu-prose-first-last font-semibold !mt-2 mb-4 md:mb-6 relative after:absolute after:h-px after:bottom-0 after:bg-cu-red after:left-px text-3xl md:text-4xl lg:text-5xl lg:leading-[3.5rem] pb-5 after:w-10 text-cu-black-700 not-prose\">\n                        TR-96-14: Symmetries and Sense of Direction in Labeled Graphs\n                    <\/h1>\n                \n                                \n                            <\/header>\n\n                    <\/div>\n\n            <\/div>\n\n    <\/div>\n<\/section>\n\n<p>Carleton University<br>\n<a href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/\">Technical Report<\/a> TR-96-14<br>\nApril&nbsp;1996<\/p>\n\n\n\n<h2 id=\"symmetries-and-sense-of-direction-in-labeled-graphs\" class=\"wp-block-heading tr_t1\">Symmetries and Sense of Direction in Labeled Graphs<\/h2>\n\n\n\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">\n<div class=\"tr_t3\">Paola Flocchini, Alessandro Roncato, Nicola Santoro<\/div>\n<\/div>\n<div>\n<h3>Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n<div class=\"tr_abstract\">\n<p>We consider distributed systems modeled by edge-labeled graphs. Properties of the labeling can be used in the design of e\u000ecient protocols; for example, sense of direction is known to have a strong impact on the communication complexity of many distributed problems.In this paper, we analyze some relations between topology and symmetries in labeled graphs. In particular, we characterize the classes of completely symmetric and completely surrounding symmetric labeled graphs; we show that the former is a proper subset of the class of regular graphs, while the latter coincides with the class of Cayley graphs.<\/p>\n<p>We then focus on the relationship between symmetries and sense of direction. We show an interesting link between minimal sense of direction in d-regular graphs (i.e., sense of direction that uses d labels) and Cayley graphs. Namely, we prove that a regular graph has a minimal symmetrical sense of direction i\u000b it is a Cayley graph. We also discuss the relationship between minimal sense of direction and recently introduced group-based labelings.<\/p>\n<\/div>\n\n\n\n<p><a href=\"https:\/\/carleton.ca\/scs\/wp-content\/uploads\/sites\/260\/TR-96-14.pdf\">TR-96-14.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Carleton University Technical Report TR-96-14 April&nbsp;1996 Symmetries and Sense of Direction in Labeled Graphs Paola Flocchini, Alessandro Roncato, Nicola Santoro Abstract We consider distributed systems modeled by edge-labeled graphs. Properties of the labeling can be used in the design of e\u000ecient protocols; for example, sense of direction is known to have a strong impact on [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12155,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-12844","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12844","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12844"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12844\/revisions"}],"predecessor-version":[{"id":12845,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12844\/revisions\/12845"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12155"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=12844"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12844"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}