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 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...
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...
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...
An infinite word is -automatic if, for all , its st letter is the output of a deterministic automaton fed with the representation of in the considered numeration system . In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for , we state that a multidimensional infinite word over a finite alphabet is -automatic for some abstract numeration...
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 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...