A Graph-Theoretic Approach to a Communications Problem
Gary Chartrand · SIAM Journal on Applied Mathematics · 1966
Previous article Next article A Graph-Theoretic Approach to a Communications ProblemGary ChartrandGary Chartrandhttps://doi.org/10.1137/0114065PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout[1] Claude Berge, The theory of graphs and its applications, Translated by Alison Doig, Methuen & Co. Ltd., London, 1962x+247 MR0132541 (24:A2381) 0097.38903 Google Scholar[2] F. Harary, Combinatorial problems in graphical enumerationApplied Combinatorial Mathematics, Wiley, New York, 1964, 185–217 0158.20801 Google Scholar[3] Frank Harary, Some historical and intuitive aspects of graph theory, SIAM Rev., 2 (1960), 123–131 10.1137/1002023 MR0111698 (22:2560) 0090.13203 LinkISIGoogle Scholar[4] Oystein Ore, Theory of graphs, American Mathematical Society Colloquium Publications, Vol. XXXVIII, American Mathematical Society, Providence, R.I., 1962x+270 MR0150753 (27:740) 0105.35401 CrossrefGoogle Scholar Previous article Next article FiguresRelatedReferencesCited ByDetails Edge-connectivity in hypergraphsIndian Journal of Pure and Applied Mathematics, Vol. 84 | 16 July 2021 Cross Ref Sparse Sachdev-Ye-Kitaev model, quantum chaos, and gravity dualsPhysical Review D, Vol. 103, No. 10 | 3 May 2021 Cross Ref Edge-fault-tolerant strong Menger edge connectivity on regular graphsTheoretical Computer Science, Vol. 847 | 1 Dec 2020 Cross Ref Super Edge-Connected Linear HypergraphsParallel Processing Letters, Vol. 30, No. 03 | 12 October 2020 Cross Ref Degree Sequence Conditions for Maximally Edge-Connected and Super Edge-Connected HypergraphsGraphs and Combinatorics, Vol. 36, No. 4 | 11 April 2020 Cross Ref Sufficient conditions for optimally and super m -restricted edge-connected graphs with given girthLinear and Multilinear Algebra, Vol. 70 | 22 April 2020 Cross Ref Super-Edge-Connectivity and Zeroth-Order Randić IndexJournal of the Operations Research Society of China, Vol. 7, No. 4 | 3 October 2018 Cross Ref Sufficient Conditions for Maximally Edge-connected and Super-edge-connected Digraphs Depending on the SizeActa Mathematica Sinica, English Series, Vol. 35, No. 12 | 15 November 2019 Cross Ref Designs with blocks of size two and applications to microarray experimentsThe Annals of Statistics, Vol. 46, No. 6A | 1 Dec 2018 Cross Ref Super Edge-connectivity and Zeroth-order General Randić Index for −1 ≤ α < 0Acta Mathematicae Applicatae Sinica, English Series, Vol. 34, No. 4 | 4 October 2018 Cross Ref On the minimum degree, edge-connectivity and connectivity of power graphs of finite groupsCommunications in Algebra, Vol. 46, No. 7 | 18 January 2018 Cross Ref Cascading Failures on Reliability in Cyber-Physical SystemIEEE Transactions on Reliability, Vol. 65, No. 4 | 1 Dec 2016 Cross Ref Efficient k-edge connected component detection through an early merging and splitting strategyKnowledge-Based Systems, Vol. 111 | 1 Nov 2016 Cross Ref Edge connectivity and super edge-connectivity of jump graphsJournal of Information and Optimization Sciences, Vol. 37, No. 2 | 18 April 2016 Cross Ref Multivariate Algorithmics for Finding Cohesive SubnetworksAlgorithms, Vol. 9, No. 1 | 16 March 2016 Cross Ref Parameterized Algorithmics for Graph Modification Problems: On Interactions with HeuristicsGraph-Theoretic Concepts in Computer Science | 5 August 2016 Cross Ref Maximally edge-connected graphs and Zeroth-order general Randić index for $$\alpha \le -1$$ α ≤ - 1Journal of Combinatorial Optimization, Vol. 31, No. 1 | 11 March 2014 Cross Ref Maximally edge-connected hypergraphsDiscrete Mathematics, Vol. 339, No. 1 | 1 Jan 2016 Cross Ref Star complements and edge-connectivity in finite graphsLinear Algebra and its Applications, Vol. 476 | 1 Jul 2015 Cross Ref Finding Highly Connected SubgraphsSOFSEM 2015: Theory and Practice of Computer Science | 1 Jan 2015 Cross Ref Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge CoverageIEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 11, No. 3 | 1 May 2014 Cross Ref Maximally edge-connected graphs and Zeroth-order general Randić index for 0<α<1Discrete Applied Mathematics, Vol. 167 | 1 Apr 2014 Cross Ref Further Topics in ConnectivityHandbook of Graph Theory, Second Edition | 26 November 2013 Cross Ref Codes from incidence matrices of graphsDesigns, Codes and Cryptography, Vol. 68, No. 1-3 | 3 January 2012 Cross Ref Vulnerability and economic considerations in designing network topology2013 International Conference on QiR | 1 Jun 2013 Cross Ref Connectivity and Depth First SearchGraphs, Networks and Algorithms | 1 Jan 2013 Cross Ref Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge CoverageBioinformatics Research and Applications | 1 Jan 2013 Cross Ref Inverse degree and super edge-connectivityInternational Journal of Computer Mathematics, Vol. 89, No. 6 | 1 Apr 2012 Cross Ref Super λ3 -optimality of regular graphsApplied Mathematics Letters, Vol. 25, No. 2 | 1 Feb 2012 Cross Ref Connectivity and MatchingGraphs: Theory and Algorithms | 22 February 2011 Cross Ref A generalization of an edge-connectivity theorem of ChartrandNetworks, Vol. 54, No. 2 | 1 Sep 2009 Cross Ref Sufficient degree conditions for k -edge-connectedness of a graphNetworks, Vol. 54, No. 2 | 1 Sep 2009 Cross Ref Inverse degree and edge-connectivityDiscrete Mathematics, Vol. 309, No. 9 | 1 May 2009 Cross Ref On super edge-connectivity of product graphsApplied Mathematics and Computation, Vol. 207, No. 2 | 1 Jan 2009 Cross Ref SkyGraph: an algorithm for important subgraph discovery in relational graphsData Mining and Knowledge Discovery, Vol. 17, No. 1 | 17 July 2008 Cross Ref Maximally edge-connected and vertex-connected graphs and digraphs: A surveyDiscrete Mathematics, Vol. 308, No. 15 | 1 Aug 2008 Cross Ref Local-edge-connectivity in digraphs and oriented graphsDiscrete Mathematics, Vol. 307, No. 24 | 1 Nov 2007 Cross Ref On the edge-connectivity and restricted edge-connectivity of a product of graphsDiscrete Applied Mathematics, Vol. 155, No. 18 | 1 Nov 2007 Cross Ref Sufficient conditions for restricted-edge-connectivity to be optimalDiscrete Mathematics, Vol. 307, No. 22 | 1 Oct 2007 Cross Ref Degree conditions for restricted-edge-connectivity and isoperimetric-edge-connectivity to be optimalDiscrete Mathematics, Vol. 307, No. 2 | 1 Jan 2007 Cross Ref Sufficient conditions for graphs to be ??-optimal, super-edge-connected, and maximally edge-connectedJournal of Graph Theory, Vol. 48, No. 3 | 1 January 2005 Cross Ref Degree sequence conditions for equal edge-connectivity and minimum degree, depending on the clique numberJournal of Graph Theory, Vol. 42, No. 3 | 12 February 2003 Cross Ref Realizability ofp-point,q-line graphs with prescribed maximum degree and line connectivity or minimum degreeNetworks, Vol. 36, No. 1 | 1 January 2000 Cross Ref On the order and size of s-geodetic digraphs with given connectivityDiscrete Mathematics, Vol. 174, No. 1-3 | 1 Sep 1997 Cross Ref How to find overfull subgraphs in graphs with large maximum degreeDiscrete Applied Mathematics, Vol. 51, No. 1-2 | 1 Jun 1994 Cross Ref On the edge-toughness of a graph. IIJournal of Graph Theory, Vol. 17, No. 2 | 1 Jun 1993 Cross Ref On super-edge-connected digraphs and bipartite digraphsJournal of Graph Theory, Vol. 16, No. 6 | 1 Dec 1992 Cross Ref Relations between parameters of a graphDiscrete Mathematics, Vol. 89, No. 1 | 1 May 1991 Cross Ref Reliability Measures for Large SystemsInternational Journal of Quality & Reliability Management, Vol. 7, No. 6 | 1 Jun 1990 Cross Ref Edge-connectivity in p-partite graphsJournal of Graph Theory, Vol. 13, No. 1 | 1 Mar 1989 Cross Ref The connected cutset connectivity of a graphDiscrete Mathematics, Vol. 69, No. 3 | 1 May 1988 Cross Ref Graphs and degree sequences. ICybernetics, Vol. 23, No. 6 | 1 Jan 1988 Cross Ref On Minimum Critically n-Edge-Connected GraphsMargaret B. Cozzens and Shu-Shih Y. WuSIAM Journal on Algebraic Discrete Methods, Vol. 8, No. 4 | 17 July 2006AbstractPDF (1017 KB)Lower-bounds on the connectivities of a graphJournal of Graph Theory, Vol. 9, No. 4 | 1 Jan 1985 Cross Ref A compilation of relations between graph invariantsNetworks, Vol. 15, No. 1 | 1 Jan 1985 Cross Ref An extremal problem on the connectivity of graphsNetworks, Vol. 14, No. 2 | 1 Jan 1984 Cross Ref Conditional connectivityNetworks, Vol. 13, No. 3 | 1 Jan 1983 Cross Ref A new algorithm to compute vertex cutsets in a graphComputers & Electrical Engineering, Vol. 8, No. 4 | 1 Dec 1981 Cross Ref Realizability ofp-point graphs with prescribed minimum degree, maximum degree, and line connectivityJournal of Graph Theory, Vol. 4, No. 4 | 1 Jan 1980 Cross Ref A sufficient condition for equality of edge-connectivity and minimum degree of a graphJournal of Graph Theory, Vol. 3, No. 3 | 1 Jan 1979 Cross Ref On graphs with equal edge connectivity and minimum degreeDiscrete Mathematics, Vol. 28, No. 3 | 1 Jan 1979 Cross Ref A Generalization of Line Connectivity and Optimally Invulnerable GraphsF. T. Boesch and S. ChenSIAM Journal on Applied Mathematics, Vol. 34, No. 4 | 12 July 2006AbstractPDF (650 KB)The minimum degree and connectivity of a graphTheory and Applications of Graphs | 30 August 2006 Cross Ref On graphs with equal edge-connectivity and minimum degreeDiscrete Mathematics, Vol. 23, No. 1 | 1 Jan 1978 Cross Ref Graph theory applied to optimal connectivity in computer networksACM SIGCOMM Computer Communication Review, Vol. 7, No. 2 | 1 Apr 1977 Cross Ref Results on the edge-connectivity of graphsDiscrete Mathematics, Vol. 8, No. 4 | 1 Jan 1974 Cross Ref Regular stochastic matrices and digraphsJournal of Applied Probability, Vol. 10, No. 01 | 14 July 2016 Cross Ref Regular stochastic matrices and digraphsJournal of Applied Probability, Vol. 10, No. 1 | 14 July 2016 Cross Ref Analysis and Design of Reliable Computer NetworksIEEE Transactions on Communications, Vol. 20, No. 3 | 1 Jun 1972 Cross Ref A general class of invulnerable graphsNetworks, Vol. 2, No. 3 | 1 Jan 1972 Cross Ref Lower bounds on the vulnerability of a graphNetworks, Vol. 2, No. 4 | 1 Jan 1972 Cross Ref On the Invulnerability of the Regular Complete k-Partite GraphsF. T. Boesch and A. FelzerSIAM Journal on Applied Mathematics, Vol. 20, No. 2 | 12 July 2006AbstractPDF (657 KB)The connectivity and line-connectivity of complementary graphsRecent Trends in Graph Theory | 19 August 2006 Cross Ref Connectivity in digraphsRecent Trends in Graph Theory | 19 August 2006 Cross Ref Analysis and Design of Survivable NetworksIEEE Transactions on Communications, Vol. 18, No. 5 | 1 Oct 1970 Cross Ref GRAPH CONNECTIVITY ALGORITHMAnnals of the New York Academy of Sciences, Vol. 175, No. 1 The Impac of | 1 Jul 1970 Cross Ref GRAPH CONNECTIVITY ALGORITHMAnnals of the New York Academy of Sciences, Vol. 175, No. 1 | 1 Jul 1970 Cross Ref Critically and minimally n-connected graphsThe Many Facets of Graph Theory | 22 August 2006 Cross Ref Volume 14, Issue 4| 1966SIAM Journal on Applied Mathematics641-959 History Submitted:15 July 1965Published online:03 August 2006 InformationCopyright © 1966 © Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0114065Article page range:pp. 778-781ISSN (print):0036-1399ISSN (online):1095-712XPublisher:Society for Industrial and Applied Mathematics