Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Dominating set (2)
- Vizing's conjecture (2)
- 2-dominating set (1)
- 2-domination number (1)
- Almost bipartite graph (1)
-
- Arrangement of points (1)
- Burning number (1)
- Cartesian product (1)
- Cartesian product graph (1)
- Cartesian product of graphs (1)
- Channel assignment problem (1)
- Circular caterpillar (1)
- Coloring (1)
- Complete bipartite graph (1)
- Complete multipartite graph (1)
- Cyclic decomposition (1)
- D-divisible alpha labeling (1)
- Digraph (1)
- Directed graph (1)
- Distance (1)
- Domination (1)
- Domination number (1)
- Equidistant tree (1)
- Finite ultrametric space (1)
- Gamma labeling (1)
- Graham's conjecture (1)
- Graph algorithms (1)
- Graph pebbling (1)
- Graph saturation; extremal graph theory (1)
- Integer domination (1)
Articles 1 - 12 of 12
Full-Text Articles in Physical Sciences and Mathematics
Addendum For The Article Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia
Addendum For The Article Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia
Theory and Applications of Graphs
Additional references listed for the article: Saha, Laxman and Basunia, Alamgir Rahaman (2020) "Radio Graceful Labelling of Graphs," Theory and Applications of Graphs: Vol. 7: Iss. 1, Article 7. DOI: 10.20429/tag.2020.070107
Isomorphism Of Trees And Isometry Of Ultrametric Spaces, Oleksiy Dovgoshey
Isomorphism Of Trees And Isometry Of Ultrametric Spaces, Oleksiy Dovgoshey
Theory and Applications of Graphs
We study the conditions under which the isometry of spaces with metrics generated by weights given on the edges of finite trees is equivalent to the isomorphism of these trees. Similar questions are studied for ultrametric spaces generated by labelings given on the vertices of trees. The obtained results generalized some facts previously known for phylogenetic trees and for Gurvich---Vyalyi monotone trees.
Decomposition Of Certain Complete Graphs And Complete Multipartite Graphs Into Almost-Bipartite Graphs And Bipartite Graphs, G. Sethuraman, M. Sujasree
Decomposition Of Certain Complete Graphs And Complete Multipartite Graphs Into Almost-Bipartite Graphs And Bipartite Graphs, G. Sethuraman, M. Sujasree
Theory and Applications of Graphs
In his classical paper [14], Rosa introduced a hierarchical series of labelings called ρ, σ, β and α labeling as a tool to settle Ringel’s Conjecture which states that if T is any tree with m edges then the complete graph K2m+1 can be decomposed into 2m + 1 copies of T . Inspired by the result of Rosa [14] many researchers significantly contributed to the theory of graph decomposition using graph labeling. In this direction, in 2004, Blinco et al. [6] introduced γ-labeling as a stronger version of ρ-labeling. A function g defined on the vertex set …
Laplacian Spectral Properties Of Signed Circular Caterpillars, Maurizio Brunetti
Laplacian Spectral Properties Of Signed Circular Caterpillars, Maurizio Brunetti
Theory and Applications of Graphs
A circular caterpillar of girth n is a graph such that the removal of all pendant vertices yields a cycle Cn of order n. A signed graph is a pair Γ =(G,σ), where G is a simple graph and σ: E(G) →{+1, -1} is the sign function defined on the set E(G) of edges of G. The signed graph Γ is said to be balanced if the number of negatively signed edges in each cycle is even, and it is said to be unbalanced otherwise. We determine some bounds for the first n Laplacian eigenvalues …
The Burning Number Of Directed Graphs: Bounds And Computational Complexity, Remie Janssen
The Burning Number Of Directed Graphs: Bounds And Computational Complexity, Remie Janssen
Theory and Applications of Graphs
The burning number of a graph was recently introduced by Bonato et al. Although they mention that the burning number generalizes naturally to directed graphs, no further research on this has been done. Here, we introduce graph burning for directed graphs, and we study bounds for the corresponding burning number and the hardness of finding this number. We derive sharp bounds from simple algorithms and examples. The hardness question yields more surprising results: finding the burning number of a directed tree with one indegree-0 node is NP-hard, but FPT; however, it is W[2]-complete for DAGs. Finally, we give a fixed-parameter …
Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia
Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia
Theory and Applications of Graphs
Radio labelling problem of graphs have their roots in communication problem known as Channel Assignment Problem. For a simple connected graph G=(V(G), E(G)), a radio labeling is a mapping f : V(G) →{0,1,2,…} such that |f(u)-f(v)|≥ diam(G)+1-d(u,v) for each pair of distinct vertices u,v ∈ V(G), where diam(G) is the diameter of G and d(u,v) is the distance between u and v. A radio labeling f of a graph G is a radio graceful labeling of G if f(V(G)) = {0,1,… |V(G)|-1}. A graph for which a radio graceful labeling exists is called radio graceful. …
Domination Number Of Annulus Triangulations, Toshiki Abe, Junki Higa, Shin-Ichi Tokunaga
Domination Number Of Annulus Triangulations, Toshiki Abe, Junki Higa, Shin-Ichi Tokunaga
Theory and Applications of Graphs
An annulus triangulation G is a 2-connected plane graph with two disjoint faces f1 and f2 such that every face other than f1 and f2 are triangular, and that every vertex of G is contained in the boundary cycle of f1 or f2. In this paper, we prove that every annulus triangulation G with t vertices of degree 2 has a dominating set with cardinality at most ⌊ \frac{|V(G)|+t+1}{4} ⌋ if G is not isomorphic to the octahedron. In particular, this bound is best possible.
An Improvement In The Two-Packing Bound Related To Vizing's Conjecture, Kimber Wolff
An Improvement In The Two-Packing Bound Related To Vizing's Conjecture, Kimber Wolff
Theory and Applications of Graphs
Vizing's conjecture states that the domination number of the Cartesian product of graphs is at least the product of the domination numbers of the two factor graphs. In this note we improve the recent bound of Breŝar by applying a technique of Zerbib to show that for any graphs G and H, γ(G x H)≥ γ (G) 2/3(γ(H)-ρ(H)+1), where γ is the domination number, ρ is the 2-packing number, and x is the Cartesian product.
On A Vizing-Type Integer Domination Conjecture, Elliot Krop, Randy R. Davila
On A Vizing-Type Integer Domination Conjecture, Elliot Krop, Randy R. Davila
Theory and Applications of Graphs
Given a simple graph G, a dominating set in G is a set of vertices S such that every vertex not in S has a neighbor in S. Denote the domination number, which is the size of any minimum dominating set of G, by γ(G). For any integer k ≥ 1, a function f : V (G) → {0, 1, . . ., k} is called a {k}-dominating function if the sum of its function values over any closed neighborhood is at least k. The weight of a {k}-dominating function is the sum of its values over all …
Recursive Formulas For Beans Functions Of Graphs, Kengo Enami, Seiya Negami
Recursive Formulas For Beans Functions Of Graphs, Kengo Enami, Seiya Negami
Theory and Applications of Graphs
In this paper, we regard each edge of a connected graph G as a line segment having a unit length, and focus on not only the "vertices" but also any "point" lying along such a line segment. So we can define the distance between two points on G as the length of a shortest curve joining them along G. The beans function BG(x) of a connected graph G is defined as the maximum number of points on G such that any pair of points have distance at least x>0. We shall show a recursive formula for …
Triangles In Ks-Saturated Graphs With Minimum Degree T, Craig Timmons, Benjamin Cole, Albert Curry, David Davini
Triangles In Ks-Saturated Graphs With Minimum Degree T, Craig Timmons, Benjamin Cole, Albert Curry, David Davini
Theory and Applications of Graphs
For n ≥ 15, we prove that the minimum number of triangles in an n-vertex K4-saturated graph with minimum degree 4 is exactly 2n-4, and that there is a unique extremal graph. This is a triangle version of a result of Alon, Erdos, Holzman, and Krivelevich from 1996. Additionally, we show that for any s > r ≥ 3 and t ≥ 2 (s-2)+1, there is a Ks-saturated n-vertex graph with minimum degree t that has \binom{ s-2}{r-1}2^{r-1} n + c_{s,r,t} copies of Kr. This shows that …
Graham's Pebbling Conjecture Holds For The Product Of A Graph And A Sufficiently Large Complete Graph, Nopparat Pleanmani
Graham's Pebbling Conjecture Holds For The Product Of A Graph And A Sufficiently Large Complete Graph, Nopparat Pleanmani
Theory and Applications of Graphs
For connected graphs G and H, Graham conjectured that π(G □ H) ≤ π(G) π(H) where π(G), π (H), and π(G □ H) are the pebbling numbers of G, H, and the Cartesian product G □ H, respectively. In this paper, we show that the inequality holds when H is a complete graph of sufficiently large order in terms of graph parameters of G.