Degree diameter problem
ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿ, ಡಿಗ್ರಿ ವ್ಯಾಸದ ಸಮಸ್ಯೆಯು ವ್ಯಾಸದ ಅತಿದೊಡ್ಡ ಗ್ರಾಫ್ ಅನ್ನು (ಅದರ ಶೃಂಗದ ಗುಂಪಿನ ಗಾತ್ರದ ದೃಷ್ಟಿಯಿಂದ) ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯಾಗಿದ್ದು, ಯಾವುದೇ ಶೃಂಗಗಳ ಅತಿದೊಡ್ಡ ಡಿಗ್ರಿ ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ಅದರ ಗಾತ್ರವು ಮೂರ್ ಬೌಂಡ್ನಿಂದ ಮೇಲೆ ಸುತ್ತುವರಿಯಲ್ಪಟ್ಟಿದೆ; ಏಕೆಂದರೆ ಪೀಟರ್ಸನ್ ಗ್ರಾಫ್, ಹಾಫ್ಮನ್-ಸಿಂಗ್ಲೆಟನ್ ಗ್ರಾಫ್ ಮತ್ತು ವ್ಯಾಸ ಮತ್ತು ಡಿಗ್ರಿಯ ಗ್ರಾಫ್ಗಳು (ಇನ್ನೂ ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ ಎಂದು ಸಾಬೀತಾಗಿದೆ) ಮಾತ್ರ ಮೂರ್ ಬೌಂಡ್ ಅನ್ನು ತಲುಪುತ್ತವೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಅತಿದೊಡ್ಡ ಡಿಗ್ರಿ-ವ್ಯಾಸದ ಗ್ರಾಫ್ಗಳು ಮೂರ್ ಬೌಂಡ್ಗಿಂತ ಗಾತ್ರದಲ್ಲಿ ಚಿಕ್ಕದಾಗಿರುತ್ತವೆ. ಸೂತ್ರವು ಗರಿಷ್ಠ ಡಿ ಮತ್ತು ವ್ಯಾಸ ಕೆ ಇರುವ ಗ್ರಾಫ್ಗೆ ಸಾಧ್ಯವಾದ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಶೃಂಗಗಳಾಗಿರಲಿ. ನಂತರ, ಮೂರ್ ಬೌಂಡ್ ಎಲ್ಲಿದೆಃ ಈ ಬೌಂಡ್ ಅನ್ನು ಕೆಲವೇ ಗ್ರಾಫ್ಗಳಿಗೆ ಸಾಧಿಸಲಾಗುತ್ತದೆ, ಹೀಗಾಗಿ ಅಧ್ಯಯನವು ಮೂರ್ ಬೌಂಡ್ಗೆ ಎಷ್ಟು ಹತ್ತಿರದಲ್ಲಿ ಗ್ರಾಫ್ಗಳಿವೆ ಎಂಬುದಕ್ಕೆ ಚಲಿಸುತ್ತದೆ. ಅಸಿಂಪ್ಟೋಟಿಕ್ ನಡವಳಿಕೆಗಾಗಿ ಅದನ್ನು ಗಮನಿಸಿ. ನಿಯತಾಂಕವನ್ನು ವ್ಯಾಖ್ಯಾನಿಸಿ. ಎಲ್ಲರಿಗೂ ಅದು ಮತ್ತು ಅದು ತಿಳಿದಿದೆ ಎಂದು ಊಹಿಸಲಾಗಿದೆ. ಕೇಜ್ (ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತ) ಕೋಷ್ಟಕವನ್ನು ಸಹ ನೋಡಿ ಒಂದು ನಿರ್ದಿಷ್ಟ ವ್ಯಾಸ ಮತ್ತು ಗರಿಷ್ಠ ಡಿಗ್ರಿಗಳ ಅತಿದೊಡ್ಡ ಗ್ರಾಫ್ಗಳ ಕೋಷ್ಟಕ ಶೃಂಗ-ಸಮಮಿತಿಯ ಡಿಗ್ರಿ ವ್ಯಾಸದ ಡಿಗ್ರ್ಯಾಫ್ಗಳ ಕೋಷ್ಟಕ ಗರಿಷ್ಠ ಡಿಗ್ರಿ-ಮತ್ತು-ವ್ಯಾಸ-ಸುತ್ತುವರಿದ ಉಪಗ್ರಾಫ್ ಸಮಸ್ಯೆಯ ಉಲ್ಲೇಖಗಳು ಗ್ರಾಫ್ ಸಿದ್ಧಾಂತದಲ್ಲಿನ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಗಳು ಗ್ರಾಫ್ ದೂರ