On Complementary Graphs

DOI10.2307/2306658zbMath0070.18503OpenAlexW2319043422MaRDI QIDQ3231818

E. A. Nordhaus, Jerry W. Gaddum

Publication date: 1956

Published in: The American Mathematical Monthly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2306658

zbMATH Keywords

topology

Related Items

Bidegree of graph and degeneracy number, Nordhaus-Gaddum problems for power domination, Nordhaus-Gaddum results for the induced path number of a graph when neither the graph nor its complement contains isolates, On incidence energy of a graph, Some progress on the double Roman domination in graphs, Split graphs and Nordhaus-Gaddum graphs, Some parameters of graph and its complement, The rainbow vertex-index of complementary graphs, Total rainbow connection number and complementary graph, On the signed total Roman domination and domatic numbers of graphs, On geometric-arithmetic index, The diversity of domination, Maximum size of digraphs with some parameters, On strong (weak) independent sets and vertex coverings of a graph, On the product of upper irredundance numbers of a graph and its complement, Nordhaus-Gaddum-type theorem for rainbow connection number of graphs, Inequalities between the domination number and the chromatic number of a graph, On upper bounds for the pseudo-achromatic index, Bounds on the (Laplacian) spectral radius of graphs, A new like quantity based on ``Estrada index, Inequalities of Nordhaus-Gaddum type for doubly connected domination number, The bipartite edge frustration of composite graphs, Nordhaus-Gaddum type result for the matching number of a graph, Nordhaus-Gaddum theorem for the distinguishing chromatic number, On ordinary generalized geometric-arithmetic index, Super dominating sets in graphs, Inequalities for the chromatic numbers of graphs, Domination in 4-regular graphs with girth 3, Nordhaus-Gaddum type inequalities for Laplacian and signless Laplacian eigenvalues, Nordhaus-Gaddum for treewidth, Nordhaus-Gaddum-type problems for lines in hypergraphs, Improper C-colorings of graphs, Nordhaus-Gaddum bounds for total Roman domination, On completely positive graphs and their complements, Multiple factor Nordhaus-Gaddum type results for domination and total domination, Sphere representations, stacked polytopes, and the Colin de Verdière number of a graph, Generalized k-tuple colorings of cycles and other graphs, Graphs which, with their complements, have certain clique covering numbers, On the Laplacian spectral radius of a graph, On the equality of the partial Grundy and upper ochromatic numbers of graphs, Nordhaus-Gaddum-type theorem for Wiener index of graphs when decomposing into three parts, New Nordhaus-Gaddum-type results for the Kirchhoff index, Nordhaus-Gaddum-type theorem for total-proper connection number of graphs, Using size for bounding expressions of graph invariants, A note on Nordhaus-Gaddum inequalities for domination., A Nordhaus-Gaddum conjecture for the minimum number of distinct eigenvalues of a graph, Extremal properties of reciprocal complementary Wiener number of trees, Extremal regular graphs for the achromatic number, On conflict-free connection of graphs, The signed Roman \(k\)-domatic number of a graph, Connected domination number of a graph and its complement, Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph, The product of the independent domination numbers of a graph and its complement, The Roman \(\{2 \}\)-domatic number of graphs, On Nordhaus-Gaddum type inequalities for the game chromatic and game coloring numbers, On edge-rupture degree of graphs, On reciprocal molecular topological index, The Nordhaus-Gaddum-type inequality for the Wiener polarity index, On rainbow total-coloring of a graph, Some results on the reciprocal sum-degree distance of graphs, More bounds for the Grundy number of graphs, Tight Nordhaus-Gaddum-type upper bound for total-rainbow connection number of graphs, Choice number and energy of graphs, Harmonious colourings of graphs, On Hadwiger's number---A problem of the Nordhaus-Gaddum type, Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number, On (distance) Laplacian energy and (distance) signless Laplacian energy of graphs, Some extremal results on the colorful monochromatic vertex-connectivity of a graph, Bounded vertex colorings of graphs, An inertial lower bound for the chromatic number of a graph, A survey of automated conjectures in spectral graph theory, On the graph complement conjecture for minimum semidefinite rank, On Harary index, The Nordhaus-Gaddum-type inequalities for the Zagreb index and co-index of graphs, Nordhaus-Gaddum relations for proximity and remoteness in graphs, The diachromatic number of digraphs, Proper connection numbers of complementary graphs, The vertex-rainbow index of a graph, Nordhaus-Gaddum-type results for resistance distance-based graph invariants, Graphs with no induced \(C_ 4\) and \(2K_ 2\), Beyond graph energy: norms of graphs and matrices, Nordhaus-Gaddum-type relations of three graph coloring parameters, Open problems on graph eigenvalues studied with AutoGraphiX, Some relations between rank, chromatic number and energy of graphs, Chromatic partitions of a graph, Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers, On reciprocal complementary Wiener number, On the algorithmic complexity of twelve covering and independence parameters of graphs, Signed domination numbers of a graph and its complement, Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum, Estimating the Szeged index, Nordhaus-Gaddum type inequalities for some distance-based indices of bipartite molecular graphs, More on limited packings in graphs, Nordhaus-Gaddum-type relations for arithmetic-geometric spectral radius and energy, On a Nordhaus-Gaddum type problem for independent domination, Extremal graphs in some coloring problems, Ordered colourings of graphs, Restrained domination in graphs, Graph factorization and theorems of the Nordhaus-Gaddum class, Relations between parameters of a graph, On the chromatic vertex stability number of graphs, Nordhaus-Gaddum inequalities for the number of connected induced subgraphs in graphs, NORDHAUS–GADDUM-TYPE THEOREM FOR DIAMETER OF GRAPHS WHEN DECOMPOSING INTO MANY PARTS, LIST POINT ARBORICITY OF GRAPHS, The Laplacian spread of graphs, Ramsey numbers for degree monotone paths, The digrundy number of digraphs, On (distance) signless Laplacian spectra of graphs, Strength and fractional arboricity of complementary graphs, On the perfect differential of a graph, More on the rainbow disconnection in graphs, On strong metric dimension of graphs and their complements, Unnamed Item, On three outer-independent domination related parameters in graphs, Total domination number of middle graphs, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, Remarks on odd colorings of graphs, Some Nordhaus-Gaddum type results of \(A_\alpha \)-eigenvalues of weighted graphs, The Connectivity of a Bipartite Graph and Its Bipartite Complementary Graph, Nordhaus-Gaddum bounds for upper total domination, Nordhaus-Gaddum inequalities for domination in graphs, The signed total Roman \(k\)-domatic number of a graph, A Nordhaus-Gaddum-type result for the induced path number, Nordhaus-Gaddum type inequalities of the second \(A_\alpha\)-eigenvalue of a graph, Some bounds for total communicability of graphs, On the hyperbolicity constant of circular-arc graphs, Clique coverings and claw-free graphs, Bounding the pseudoachromatic index of the complete graph via projective planes, Rainbow connections of graphs: a survey, The double Roman domatic number of a digraph, The Wiener index of the \(k\)th power of a graph, Nordhaus-Gaddum results for the sum of the induced path number of a graph and its complement, Nordhaus-Gaddum bounds for total domination, Inequality of Nordhaus-Gaddum type for total outer-connected domination in graphs, Some chemical indices related to the number of triangles, Improving upper bounds for the distinguishing index, Monochromatic disconnection of graphs, Graphs with large Italian domination number, Inequalities for the first-fit chromatic number, On incidence energy of graphs, Study of the Bipartite Edge Frustration of Graphs, Unnamed Item, On a new cyclicity measure of graphs -- the global cyclicity index, More eigenvalue problems of Nordhaus-Gaddum type, The product of the restrained domination numbers of a graph and its complement, Nordhaus-Gaddum results for the convex domination number of a graph, The signed total Roman domatic number of a digraph, Unnamed Item, Unnamed Item, THE HYPER-WIENER INDEX OF THE kth POWER OF A GRAPH, Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs, Unnamed Item, Distance spectra of graphs: a survey, Nordhaus-Gaddum-type results for path covering and \(L(2,1)\)-labeling numbers, CMMSE 18: geometric-arithmetic index and line graph, The tree-covering number of a graph, Regular number of a graph, Nordhaus-Gaddum type results for graph irregularities, Extension of a list coloring problem, The (vertex-)monochromatic index of a graph, Nordhaus-Gaddum and other bounds for the sum of squares of the positive eigenvalues of a graph, On general sum-connectivity index, On the distance signless Laplacian spectrum of graphs, Some progress on the restrained Roman domination, Signless Laplacian eigenvalue problems of Nordhaus-Gaddum type, Quasi-total Roman domination in graphs, Irregular independence and irregular domination, Toward a Nordhaus-Gaddum inequality for the number of dominating sets, The Nordhaus-Gaddum type inequalities of \(A_\alpha \)-matrix, Comparison and extremal results on three eccentricity-based invariants of graphs, On total restrained domination in graphs, On a conjecture for power domination, On the 2-packing differential of a graph, Some inequalities for the first general Zagreb index of graphs and line graphs, Restrained and Total Restrained Domination in Graphs, Distance Domination in Graphs, Roman Domination in Graphs, Unnamed Item, On the difference of energies of a graph and its complement graph, Nordhaus-Gaddum type inequalities for the distinguishing index, Eigenvalues of thek-th power of a graph, Nordhaus-Gaddum type inequalities for the two largest Laplacian eigenvalues, Nordhaus-Gaddum type inequality for the fractional matching number of a graph, On the Laplacian spectrum of \(k\)-uniform hypergraphs, Solution to a conjecture on a Nordhaus-Gaddum type result for the Kirchhoff index, Remarks on the outer-independent double Italian domination number, On \(k\)-rainbow independent domination in graphs, On the double Roman domination of graphs, Bounds on weak and strong total domination in graphs, Remarks on proper conflict-free colorings of graphs, A map colour theorem for the union of graphs, Broadcasts in graphs, The Fractional Strong Metric Dimension of Graphs, On the Nordhaus-Gaddum Problem for the k-Defective Chromatic Number of a Graph, Asteroidal Chromatic Number of a Graph, On the average of the eccentricities of a graph, On the connected metric dimension of graphs and their complements, On the domination number of a graph and its shadow graph, Further results on packing related parameters in graphs, Improving a Nordhaus-Gaddum type bound for total domination using an algorithm involving vertex disjoint stars, Unnamed Item, Unnamed Item, Unnamed Item, Coefficient of domination in graph, Extremal decompositions for Nordhaus-Gaddum theorems, On word-representable and multi-word-representable graphs, Total Italian domatic number of graphs, Generalizations of some Nordhaus–Gaddum‐type results on spectral radius, Nordhaus-Gaddum type inequality for the integer \(k\)-matching number of a graph, Transitivity on subclasses of chordal graphs, Nordhaus–Gaddum problem in terms of G-free coloring, On the edge chromatic vertex stability number of graphs, Domination in edge cycle graphs, Graph Limits and Spectral Extremal Problems for Graphs, Split graphs and block representations, Nordhaus-Gaddum type inequalities for the \(k\)th largest Laplacian eigenvalues, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Certified domination, Distance Laplacian eigenvalues and chromatic number in graphs, Signed total Italian k-domatic number of a graph, The number of spanning trees of a graph, Nordhaus-gaddum type inequalities for tree covering numbers on unitary cayley graphs of finite rings, On sum of powers of the Laplacian eigenvalues of graphs, Graph colourings and partitions, Recherche à voisinage variable de graphes extrémaux 13. à propos de la maille, The number of independent sets in a connected graph and its complement, Products of graphs and Nordhaus-Gaddum type inequalities for eigenvalues, Further properties on the degree distance of graphs, Unnamed Item, A Nordhaus–Gaddum bound for Roman domination, On zero forcing number of graphs and their complements, Highly Irregular, How to Burn a Graph, On the domination number of a graph and its total graph, Nordhaus-Gaddum-type result on the second largest signless Laplacian eigenvalue of a graph, Inequalities for real number sequences with applications in spectral graph theory