A categorification for the chromatic polynomial.
A Cauchy-Davenport type result for arbitrary regular graphs.
A census of vertices by generations in regular tessellations of the plane.
A characterization for sparse -regular pairs.
A Characterization of 2-Tree Probe Interval Graphs
A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150...
A characterization of a class of graphs connected with the hysteresis phenomena
A characterization of alternating groups by the set of orders of maximal Abelian subgroups.
A characterization of where
The order of every finite group can be expressed as a product of coprime positive integers such that is a connected component of the prime graph of . The integers are called the order components of . Some non-abelian simple groups are known to be uniquely determined by their order components. As the main result of this paper, we show that the projective symplectic groups where are also uniquely determined by their order components. As corollaries of this result, the validities of a...
A characterization of complete tripartite degree-magic graphs
A graph is called degree-magic if it admits a labelling of the edges by integers 1, 2,..., |E(G)| such that the sum of the labels of the edges incident with any vertex v is equal to (1+ |E(G)|)/2*deg(v). Degree-magic graphs extend supermagic regular graphs. In this paper we characterize complete tripartite degree-magic graphs.
A characterization of diameter-2-critical graphs with no antihole of length four
A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence...
A characterization of geodetic graphs
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