Jaroslav Ivančo (1994)
Mathematica Bohemica
Similarity:
Let the number of -element sets of independent vertices and edges of a graph be denoted by and , respectively. It is shown that the graphs whose every component is a circuit are the only graphs for which the equality is satisfied for all values of .
Lutz Volkmann (2004)
Mathematica Bohemica
Similarity:
A perfect independent set of a graph is defined to be an independent set with the property that any vertex not in has at least two neighbors in . For a nonnegative integer , a subset of the vertex set of a graph is said to be -independent, if is independent and every independent subset of with is a subset of . A set of vertices of is a super -independent set of if is -independent in the graph , where is the bipartite graph obtained from by deleting...
Ralucca Gera, Futaba Okamoto, Craig Rasmussen, Ping Zhang (2011)
Mathematica Bohemica
Similarity:
For a nontrivial connected graph , let be a vertex coloring of where adjacent vertices may be colored the same. For a vertex , the neighborhood color set is the set of colors of the neighbors of . The coloring is called a set coloring if for every pair of adjacent vertices of . The minimum number of colors required of such a coloring is called the set chromatic number . We show that the decision variant of determining is NP-complete in the general case, and show that...
Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)
Discussiones Mathematicae Graph Theory
Similarity:
Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then , and provide a characterization of graphs achieving this bound.
Jozef Bucko, Marietjie Frick, Peter Mihók, Roman Vasky (1997)
Discussiones Mathematicae Graph Theory
Similarity:
Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition of the vertex set V(G) into subsets V₁, ...,Vₙ such that the subgraph induced by has property ; i = 1,...,n. A graph G is said to be uniquely (₁, ...,ₙ)-partitionable if G has exactly one (₁,...,ₙ)-partition. A property is called hereditary if every subgraph of every graph with property also has property . If every graph that is a disjoint union of two graphs that have property also has property...
Saieed Akbari, Maryam Aliakbarpour, Naryam Ghanbari, Emisa Nategh, Hossein Shahmohamad (2014)
Czechoslovak Mathematical Journal
Similarity:
Let be a graph, and the smallest integer for which has a nowhere-zero -flow, i.e., an integer for which admits a nowhere-zero -flow, but it does not admit a -flow. We denote the minimum flow number of by . In this paper we show that if and are two arbitrary graphs and has no isolated vertex, then except two cases: (i) One of the graphs and is and the other is -regular. (ii) and is a graph with at least one isolated vertex or a component whose every...
Zhibo Chen (2010)
Czechoslovak Mathematical Journal
Similarity:
As introduced by F. Harary in 1994, a graph is said to be an if its vertices can be given a labeling with distinct integers so that for any two distinct vertices and of , is an edge of if and only if for some vertex in . We prove that every integral sum graph with a saturated vertex, except the complete graph , has edge-chromatic number equal to its maximum degree. (A vertex of a graph is said to be if it is adjacent to every...