{"id":12836,"date":"2021-11-22T18:25:41","date_gmt":"2021-11-22T23:25:41","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=12836"},"modified":"2026-06-02T14:59:25","modified_gmt":"2026-06-02T18:59:25","slug":"tr-96-10-minimal-sense-of-direction-in-regular-networks","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1996\/tr-96-10-minimal-sense-of-direction-in-regular-networks\/","title":{"rendered":"TR-96-10: Minimal Sense of Direction in Regular Networks"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-96-10: Minimal Sense of Direction in Regular Networks\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-96-10
\nMarch 1996<\/p>\n\n\n\n

A Better Upper Bound for the Unsatisfiability Threshold<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
Paola Flocchini<\/div>\n<\/div>\n
\n

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

A network is said to have Sense of Direction when the port labeling satis\fes a particular set of global consistency constraints. In this paper we study the link between the topology of a system and the number of labels that are necessary to have a Sense of Direction in that system. We consider systems whose topology is a regular graph and we study the relationship between structural properties of d-regular graphs and existence of a Sense of Direction which uses exactly d labels (minimal SD). In particular, we identify a property (Cycle Symmetricity) which we show is a necessary condition for minimal SD. Among regular graphs, we then focus on Cayley Graphs and we prove that they always have a minimal Sense of Direction.<\/p>\n<\/div>\n\n\n\n

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

Carleton University Technical Report TR-96-10 March 1996 A Better Upper Bound for the Unsatisfiability Threshold Paola Flocchini Abstract A network is said to have Sense of Direction when the port labeling satis\fes a particular set of global consistency constraints. In this paper we study the link between the topology of a system and the number […]<\/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-12836","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12836","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=12836"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12836\/revisions"}],"predecessor-version":[{"id":12837,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12836\/revisions\/12837"}],"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=12836"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=12836"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}