A characterization of graphs in which some minimum dominating set covers all the edges
A characterization of hypergraphs generated by arborescences
A Characterization of Hypergraphs with Large Domination Number
Let H = (V, E) be a hypergraph with vertex set V and edge set E. A dominating set in H is a subset of vertices D ⊆ V such that for every vertex v ∈ V D there exists an edge e ∈ E for which v ∈ e and e ∩ D ≠ ∅. The domination number γ(H) is the minimum cardinality of a dominating set in H. It is known [Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62-71] that for k ≥ 5, if H is a hypergraph of order n and size m with all...
A characterization of -closed graphs
A characterization of locating-total domination edge critical graphs
For a graph G = (V,E) without isolated vertices, a subset D of vertices of V is a total dominating set (TDS) of G if every vertex in V is adjacent to a vertex in D. The total domination number γₜ(G) is the minimum cardinality of a TDS of G. A subset D of V which is a total dominating set, is a locating-total dominating set, or just a LTDS of G, if for any two distinct vertices u and v of V(G)∖D, . The locating-total domination number is the minimum cardinality of a locating-total dominating set...
A characterization of middle graphs and a matroid associated with middle graphs of hypergraphs
A characterization of planar median graphs
Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.
A characterization of roman trees
A Roman dominating function (RDF) on a graph G = (V,E) is a function f: V → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of f is . The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number are called...
A characterization of self-complementary graphs of order 8
A characterization of semi bound graphs.
A characterization of singular graphs.
A characterization of the decay number of a connected graph
A characterization of the interval function of a connected graph
A characterization of the interval function of a (finite or infinite) connected graph
By the interval function of a finite connected graph we mean the interval function in the sense of H. M. Mulder. This function is very important for studying properties of a finite connected graph which depend on the distance between vertices. The interval function of a finite connected graph was characterized by the present author. The interval function of an infinite connected graph can be defined similarly to that of a finite one. In the present paper we give a characterization of the interval...
A characterization of the set of all shortest paths in a connected graph
Let be a (finite undirected) connected graph (with no loop or multiple edge). The set of all shortest paths in is defined as the set of all paths , then the lenght of does not exceed the length of . While the definition of is based on determining the length of a path. Theorem 1 gives - metaphorically speaking - an “almost non-metric” characterization of : a characterization in which the length of a path greater than one is not considered. Two other theorems are derived from Theorem...
A Characterization of Trees for a New Lower Bound on the K-Independence Number
Let k be a positive integer and G = (V,E) a graph of order n. A subset S of V is a k-independent set of G if the maximum degree of the subgraph induced by the vertices of S is less or equal to k − 1. The maximum cardinality of a k-independent set of G is the k-independence number βk(G). In this paper, we show that for every graph [xxx], where χ(G), s(G) and Lv are the chromatic number, the number of supports vertices and the number of leaves neighbors of v, in the graph G, respectively. Moreover,...
A characterization of (γₜ,γ₂)-trees
Let γₜ(G) and γ₂(G) be the total domination number and the 2-domination number of a graph G, respectively. It has been shown that: γₜ(T) ≤ γ₂(T) for any tree T. In this paper, we provide a constructive characterization of those trees with equal total domination number and 2-domination number.
A class of 4-pseudomanifolds similar to the lense spaces.
A class of Cayley graphs induced by right solvable ward groupoids
A class of inequalities relating degrees of adjacent nodes to the average degree in edge-weighted uniform hypergraphs.