Discrete Mathematics and Combinatorics Commons^™

Characterizing Edge Betweenness-Uniform Graphs, Jana Coroničová Hurajová, Tomas Madaras, Darren A. Narayan

Theory & Applications of Graphs

The betweenness centrality of an edge e is, summed over all u,v ∈ V(G), the ratio of the number of shortest u,v-paths in G containing e to the number of shortest u,v-paths in G. Graphs whose vertices all have the same edge betweenness centrality are called edge betweeness-uniform. It was recently shown by Madaras, Hurajová, Newman, Miranda, Fl´orez , and Narayan that of the over 11.7 million graphs with ten vertices or fewer, only four graphs are edge betweenness-uniform but not edge-transitive. In this paper we present new results involving properties of betweenness-uniform graphs.

Chromatic Polynomials Of Signed Book Graphs, Deepak Sehrawat, Bikash Bhattacharjya

Theory & Applications of Graphs

For m ≥ 3 and n ≥ 1, the m-cycle book graph B(m,n) consists of n copies of the cycle C_m with one common edge. In this paper, we prove that (a) the number of switching non-isomorphic signed B(m,n) is n+1, and (b) the chromatic number of a signed B(m,n) is either 2 or 3. We also obtain explicit formulas for the chromatic polynomials and the zero-free chromatic polynomials of switching non-isomorphic signed book graphs.

Connectedness Of Unit Distance Subgraphs Induced By Closed Convex Sets, Remie Janssen, Leonie Van Steijn

Theory & Applications of Graphs

The unit distance graph G¹_R^d is the infinite graph whose nodes are points in R^d, with an edge between two points if the Euclidean distance between these points is 1. The 2-dimensional version G¹_R2 of this graph is typically studied for its chromatic number, as in the Hadwiger-Nelson problem. However, other properties of unit distance graphs are rarely studied. Here, we consider the restriction of G¹_Rd to closed convex subsets X of R^d. We show that the graph G¹_Rd[X] is connected precisely when the radius of …

Application Of The Combinatorial Nullstellensatz To Integer-Magic Graph Labelings, Richard M. Low, Dan Roberts

Theory & Applications of Graphs

Let A be a nontrivial abelian group and A* = A \ {0}. A graph is A-magic if there exists an edge labeling f using elements of A* which induces a constant vertex labeling of the graph. Such a labeling f is called an A-magic labeling and the constant value of the induced vertex labeling is called an A-magic value. In this paper, we use the Combinatorial Nullstellensatz to show the existence of Ζ_p-magic labelings (prime p ≥ 3 ) for various graphs, without having to construct the Ζ_p-magic labelings. Through many …

Facial Achromatic Number Of Triangulations With Given Guarding Number, Naoki Matsumoto, Yumiko Ohno

Theory & Applications of Graphs

A (not necessarily proper) k-coloring c : V(G) → {1,2,…k} of a graph G on a surface is a facial t-complete k-coloring if every t-tuple of colors appears on the boundary of some face of G. The maximum number k such that G has a facial t-complete k-coloring is called a facial t-achromatic number of G, denoted by ψ_t(G). In this paper, we investigate the relation between the facial 3-achromatic number and guarding number of triangulations on a surface, where a guarding number of a graph G embedded on a surface, …

A Complete Characterisation Of Vertex-Multiplications Of Trees With Diameter 5, Willie Han Wah Wong, Eng Guan Tay

Theory & Applications of Graphs

For a connected graph G, let D(G) be the family of strong orientations of G; and for any D ∈ D(G), we denote by d(D) the diameter of D. The orientation number of G is defined as d(G)=min{d(D) | D ∈ D(G)}. In 2000, Koh and Tay introduced a new family of graphs, G vertex-multiplications, and extended the results on the orientation number of complete n-partite graphs. Suppose G has the vertex set V(G)={v₁,v₂,… v_n}. For any sequence of n positive integers (s …

Upper Bounds For Inverse Domination In Graphs, Elliot Krop, Jessica Mcdonald, Gregory J. Puleo

Theory & Applications of Graphs

In any graph G, the domination number \gamma(G) is at most the independence number \alpha(G). The Inverse Domination Conjecture says that, in any isolate-free G, there exists pair of vertex-disjoint dominating sets D, D' with |D|=\gamma(G) and |D'| \leq \alpha(G). Here we prove that this statement is true if the upper bound \alpha(G) is replaced by \frac{3}{2}\alpha(G) – 1 (and G is not a clique). We also prove that the conjecture holds whenever \gamma(G)\leq 5 or |V(G)|\leq 16.

Skolem Number Of Cycles And Grid Graphs, Braxton Carrigan, John Asplund

Theory & Applications of Graphs

A Skolem sequence can be thought of as a labelled path where two vertices with the same label are that distance apart. This concept has naturally been generalized to labellings of other graphs, but always using at most two of any integer label. Given that more than two vertices can be mutually distance d apart, we define a new generalization of a Skolem sequences on graphs that we call proper Skolem labellings. This brings rise to the question; ``what is the smallest set of consecutive positive integers we can use to proper Skolem label a graph?'' This will be known …

On \Delta^(K)-Colouring Of Powers Of Paths And Cycles, Merlin Thomas Ellumkalayil Ms, Sudev Naduvath

Theory & Applications of Graphs

In an improper vertex colouring of a graph, adjacent vertices are permitted to receive same colours. An edge of an improperly coloured graph is said to be a bad edge if its end vertices have the same colour. A near-proper colouring of a graph is a colouring which minimises the number of bad edges by restricting the number of colour classes that can have adjacency among their own elements. The δ (k) - colouring is a near-proper colouring of G consisting of k given colours, where 1 ≤ k ≤ χ(G) – 1, which minimises the number of bad …

On Graphs With Proper Connection Number 2, Jill Faudree, Leah Berman, Glenn Chappell, Chris Hartman, John Gimbel, Gordon Williams

Theory & Applications of Graphs

An edge-colored graph is properly connected if for every pair of vertices u and v there exists a properly colored uv-path (i.e. a uv-path in which no two consecutive edges have the same color). The proper connection number of a connected graph G, denoted pc(G), is the smallest number of colors needed to color the edges of G such that the resulting colored graph is properly connected. An edge-colored graph is flexibly connected if for every pair of vertices u and v there exist two properly colored paths between them, say P and Q, such …

The Color Number Of Cubic Graphs Having A Spanning Tree With A Bounded Number Of Leaves, Analen A. Malnegro, Gina A. Malacas, Kenta Ozeki

Theory & Applications of Graphs

The color number c(G) of a cubic graphG is the minimum cardinality of a color class of a proper 4-edge-coloring of G. It is well-known that every cubic graph G satisfies c(G) = 0 if G

The Structure Of Functional Graphs For Functions From A Finite Domain To Itself For Which A Half Iterate Exists, Paweł Marcin Kozyra

Theory & Applications of Graphs

The notion of a replica of a nontrivial in-tree is defined. A result enabling to determine whether an in-tree is a replica of another in-tree employing an injective mapping between some subsets of sources of these in-trees is presented. There are given necessary and sufficient conditions for the existence of a functional square root of a function from a finite set to itself through presenting necessary and sufficient conditions for the existence of a square root of a component of the functional graph for the function and for the existence of a square root of the union of two components …

Classification Of Cayley Rose Window Graphs, Angsuman Das, Arnab Mandal

Theory & Applications of Graphs

Rose window graphs are a family of tetravalent graphs, introduced by Steve Wilson. Following it, Kovacs, Kutnar and Marusic classified the edge-transitive rose window graphs and Dobson, Kovacs and Miklavic characterized the vertex transitive rose window graphs. In this paper, we classify the Cayley rose window graphs.

Reducing The Maximum Degree Of A Graph: Comparisons Of Bounds, Peter Borg

Theory & Applications of Graphs

Let λ(G) be the smallest number of vertices that can be removed from a non-empty graph G so that the resulting graph has a smaller maximum degree. Let λ_e(G) be the smallest number of edges that can be removed from G for the same purpose. Let k be the maximum degree of G, let t be the number of vertices of degree k, let M(G) be the set of vertices of degree k, let n be the number of vertices in the closed neighbourhood of M(G), and let m be the …

The Conditional Strong Matching Preclusion Of Augmented Cubes, Mohamad Abdallah, Eddie Cheng

Theory & Applications of Graphs

The strong matching preclusion is a measure for the robustness of interconnection networks in the presence of node and/or link failures. However, in the case of random link and/or node failures, it is unlikely to find all the faults incident and/or adjacent to the same vertex. This motivates Park et al. to introduce the conditional strong matching preclusion of a graph. In this paper we consider the conditional strong matching preclusion problem of the augmented cube AQ_n, which is a variation of the hypercube Q_n that possesses favorable properties.

Characterizing 2-Trees Relative To Chordal And Series-Parallel Graphs, Terry A. Mckee

Theory & Applications of Graphs

The 2-connected 2-tree graphs are defined as being constructible from a single 3-cycle by recursively appending new degree-2 vertices so as to form 3-cycles that have unique edges in common with the existing graph. Such 2-trees can be characterized both as the edge-minimal chordal graphs and also as the edge-maximal series-parallel graphs. These are also precisely the 2-connected graphs that are simultaneously chordal and series-parallel, where these latter two better-known types of graphs have themselves been both characterized and applied in numerous ways that are unmotivated by their interaction with 2-trees and with each other.

Toward providing such motivation, the …

An Efficient Algorithm To Test Potential Bipartiteness Of Graphical Degree Sequences, Kai Wang

Theory & Applications of Graphs

As a partial answer to a question of Rao, a deterministic and customizable efficient algorithm is presented to test whether an arbitrary graphical degree sequence has a bipartite realization. The algorithm can be configured to run in polynomial time, at the expense of possibly producing an erroneous output on some ``yes'' instances but with very low error rate.

Nilpotent Graph, Dhiren Kumar Basnet, Ajay Sharma, Rahul Dutta

Theory & Applications of Graphs

In this article, we introduce the concept of nilpotent graph of a finite commutative ring. The set of all non nilpotent elements of a ring is taken as the vertex set and two vertices are adjacent if and only if their sum is nilpotent. We discuss some graph theoretic properties of nilpotent graph.

The Integer-Antimagic Spectra Of Graphs With A Chord, Richard M. Low, Dan Roberts, Jinze Zheng

Theory & Applications of Graphs

Let Α be a nontrival abelian group. A connected simple graph G = (V, E) is Α-antimagic if there exists an edge labeling f: E(G) → A \ {0} such that the induced vertex labeling f+: V(G) → Α, defined by f+(v) = Σ_{{uv ∈ E(G)} f(uv), is injective. The integer-antimagic spectrum of a graph G is the set IAM(G) = {k |G is {Ζ}_k-antimagic} and k ≥2. In this paper, we determine the integer-antimagic spectra for cycles with a chord, paths with a chord, and wheels with a chord.

Addendum For The Article Radio Graceful Labelling Of Graphs, Laxman Saha, Alamgir Rahaman Basunia

Theory & 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

Theory & 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

Theory & 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

Theory & Applications of Graphs

A circular caterpillar of girth n is a graph such that the removal of all pendant vertices yields a cycle C_n 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

Theory & 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

Theory & 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

Theory & Applications of Graphs

An annulus triangulation G is a 2-connected plane graph with two disjoint faces f₁ and f₂ such that every face other than f₁ and f₂ are triangular, and that every vertex of G is contained in the boundary cycle of f₁ or f₂. 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

Theory & 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

Theory & 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

Theory & 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 B_G(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

Theory & Applications of Graphs

For n ≥ 15, we prove that the minimum number of triangles in an n-vertex K₄-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 K_s-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 K_r. This shows that …