Physical Sciences and Mathematics Commons^™

Geodesic Bipancyclicity Of The Cartesian Product Of Graphs, Amruta V. Shinde, Y.M. Borse

Theory and Applications of Graphs

A cycle containing a shortest path between two vertices u and v in a graph G is called a (u,v)-geodesic cycle. A connected graph G is geodesic 2-bipancyclic, if every pair of vertices u,v of it is contained in a (u,v)-geodesic cycle of length l for each even integer l satisfying 2d + 2 ≤ l ≤ |V(G)|, where d is the distance between u and v. In this paper, we prove that the Cartesian product of two geodesic hamiltonian graphs is a geodesic 2-bipancyclic graph. As a consequence, we show that for n …

One-Factorizations Of The Complete Graph $K_{P+1}$ Arising From Parabolas, György Kiss, Nicola Pace, Angelo Sonnino

Theory and Applications of Graphs

There are three types of affine regular polygons in AG(2, q): ellipse, hyperbola and parabola. The first two cases have been investigated in previous papers. In this note, a particular class of geometric one-factorizations of the complete graph Kn arising from parabolas is constructed and described in full detail. With the support of computer aided investigation, it is also conjectured that up to isomorphisms this is the only one-factorization where each one-factor is either represented by a line or a parabola.

Characterization Of Outerplanar Graphs With Equal 2-Domination And Domination Numbers, Naoki Matsumoto

Theory and Applications of Graphs

A k-domination number of a graph G is minimum cardinality of a k-dominating set of G, where a subset S ⊆ V(G) is a k-dominating set if each vertex v ∈ V(G) \ S is adjacent to at least k vertices in S. It is known that for any graph G with Δ(G) ≥ k ≥ 2, γ_k(G) ≥ γ(G) + k – 2, and then γk(G) > γ(G) for any k ≥ 3, where γ(G) = γ1(G) is the usual domination number. Thus, it is the most interesting problem to characterize graphs G with …

Rainbow Perfect And Near-Perfect Matchings In Complete Graphs With Edges Colored By Circular Distance, Shuhei Saitoh, Naoki Matsumoto, Wei Wu

Theory and Applications of Graphs

Given an edge-colored complete graph K_n on n vertices, a perfect (respectively, near-perfect) matching M in K_n with an even (respectively, odd) number of vertices is rainbow if all edges have distinct colors. In this paper, we consider an edge coloring of K_n by circular distance, and we denote the resulting complete graph by K^●_n. We show that when K^●_n has an even number of vertices, it contains a rainbow perfect matching if and only if n=8k or n=8k+2, where k is a nonnegative integer. In the case of an odd …

Ultrametrics And Complete Multipartite Graphs, Viktoriia Viktorivna Bilet, Oleksiy Dovgoshey, Yuriy Nikitovich Kononov

Theory and Applications of Graphs

Let (X, d) be a semimetric space and let G be a graph. We say that G is the diametrical graph of (X, d) if X is the vertex set of G and the adjacency of vertices x and y is equivalent to the equality diam X = d(x, y). It is shown that a semimetric space (X, d) with diameter d* is ultrametric if the diametrical graph of (X, d _ε) with d _ε (x, y) = min{d(x, y), ε} is complete multipartite for every ε ∈ (0, d* …

An Even 2-Factor In The Line Graph Of A Cubic Graph, Seungjae Eom, Kenta Ozeki

Theory and Applications of Graphs

An even 2-factor is one such that each cycle is of even length. A 4- regular graph G is 4-edge-colorable if and only if G has two edge-disjoint even 2- factors whose union contains all edges in G. It is known that the line graph of a cubic graph without 3-edge-coloring is not 4-edge-colorable. Hence, we are interested in whether those graphs have an even 2-factor. Bonisoli and Bonvicini proved that the line graph of a connected cubic graph G with an even number of edges has an even 2-factor, if G has a perfect matching [Even cycles and …

Prime Labelings On Planar Grid Graphs, Stephen James Curran

Theory and Applications of Graphs

It is known that for any prime p and any integer n such that 1≤n≤p there exists a prime labeling on the pxn planar grid graph P_pxP_n. We show that P_pxP_n has a prime labeling for any odd prime p and any integer n such that that p<n≤p².

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

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

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

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

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 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 …