[2210.12675] तितली नेटवर्क के लिए जियोडेसिक कवर समस्या

पॉल मैनुअल और 2 अन्य लेखकों द्वारा तितली नेटवर्क के लिए जियोडेसिक कवर समस्या शीर्षक वाले पेपर का एक पीडीएफ देखें

पीडीएफ देखें
HTML (प्रयोगात्मक)

अमूर्त:एक ग्राफ़ का जियोडेसिक कवर, जिसे आइसोमेट्रिक पथ कवर के रूप में भी जाना जाता है, जियोडेसिक्स का एक सेट है जो ग्राफ़ के शीर्ष सेट को कवर करता है। ग्राफ़ का एज जियोडेसिक कवर जियोडेसिक्स का एक सेट है जो ग्राफ़ के एज सेट को कवर करता है। ग्राफ़ की जियोडेसिक (किनारे) कवर संख्या न्यूनतम (किनारे) जियोडेसिक कवर की कार्डिनैलिटी है। ग्राफ़ की (एज) जियोडेसिक कवर समस्या ग्राफ़ की (एज) जियोडेसिक कवर संख्या ज्ञात करना है। आश्चर्य की बात यह है कि अधिकांश स्थितियों में इन समस्याओं का केवल आंशिक समाधान ही उपलब्ध है। इस पेपर में हम दर्शाते हैं कि $r$-आयामी तितली का जियोडेसिक कवर नंबर $\lceil (2/3)2^r\rceil$ है और इसका किनारा जियोडेसिक कवर नंबर $2^r$ है।