{"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":"2021-11-22T18:32:02","modified_gmt":"2021-11-22T23:32:02","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":"

Carleton University
\nTechnical Report<\/a> TR-96-14
\nApril\u00a01996<\/p>\n

Symmetries and Sense of Direction in Labeled Graphs<\/h2>\n
\n
\n
\n
\n
\n
Paola Flocchini, Alessandro Roncato, Nicola Santoro<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

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

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

TR-96-14.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-96-14 April\u00a01996 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 […]<\/p>\n","protected":false},"author":49,"featured_media":0,"parent":12155,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_mi_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":"","_links_to":"","_links_to_target":""},"yoast_head":"\nTR-96-14: Symmetries and Sense of Direction in Labeled Graphs - School of Computer Science<\/title>\n<meta name=\"description\" content=\"Carleton University Technical Report TR-96-14 April\u00a01996 Symmetries and Sense of Direction in Labeled Graphs Paola Flocchini, Alessandro Roncato, Nicola\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/\",\"url\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/\",\"name\":\"TR-96-14: Symmetries and Sense of Direction in Labeled Graphs - School of Computer Science\",\"isPartOf\":{\"@id\":\"https:\/\/carleton.ca\/scs\/#website\"},\"datePublished\":\"2021-11-22T23:32:02+00:00\",\"dateModified\":\"2021-11-22T23:32:02+00:00\",\"description\":\"Carleton University Technical Report TR-96-14 April\u00a01996 Symmetries and Sense of Direction in Labeled Graphs Paola Flocchini, Alessandro Roncato, Nicola\",\"breadcrumb\":{\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/carleton.ca\/scs\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Research\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"SCS Technical Reports\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/\"},{\"@type\":\"ListItem\",\"position\":4,\"name\":\"Technical Reports 1996\",\"item\":\"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/\"},{\"@type\":\"ListItem\",\"position\":5,\"name\":\"TR-96-14: Symmetries and Sense of Direction in Labeled Graphs\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/carleton.ca\/scs\/#website\",\"url\":\"https:\/\/carleton.ca\/scs\/\",\"name\":\"School of Computer Science\",\"description\":\"Carleton University\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/carleton.ca\/scs\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"TR-96-14: Symmetries and Sense of Direction in Labeled Graphs - School of Computer Science","description":"Carleton University Technical Report TR-96-14 April\u00a01996 Symmetries and Sense of Direction in Labeled Graphs Paola Flocchini, Alessandro Roncato, Nicola","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/","twitter_misc":{"Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/","url":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/","name":"TR-96-14: Symmetries and Sense of Direction in Labeled Graphs - School of Computer Science","isPartOf":{"@id":"https:\/\/carleton.ca\/scs\/#website"},"datePublished":"2021-11-22T23:32:02+00:00","dateModified":"2021-11-22T23:32:02+00:00","description":"Carleton University Technical Report TR-96-14 April\u00a01996 Symmetries and Sense of Direction in Labeled Graphs Paola Flocchini, Alessandro Roncato, Nicola","breadcrumb":{"@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-14-symmetries-and-sense-of-direction-in-labeled-graphs\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/carleton.ca\/scs\/"},{"@type":"ListItem","position":2,"name":"Research","item":"https:\/\/carleton.ca\/scs\/research\/"},{"@type":"ListItem","position":3,"name":"SCS Technical Reports","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/"},{"@type":"ListItem","position":4,"name":"Technical Reports 1996","item":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/"},{"@type":"ListItem","position":5,"name":"TR-96-14: Symmetries and Sense of Direction in Labeled Graphs"}]},{"@type":"WebSite","@id":"https:\/\/carleton.ca\/scs\/#website","url":"https:\/\/carleton.ca\/scs\/","name":"School of Computer Science","description":"Carleton University","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/carleton.ca\/scs\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"}]}},"acf":{"banner_image_type":"none","banner_button":"no"},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12844"}],"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\/49"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=12844"}],"version-history":[{"count":2,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12844\/revisions"}],"predecessor-version":[{"id":12846,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12844\/revisions\/12846"}],"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"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}