Physical Sciences and Mathematics Commons^™

Strongly I-Bicritical Graphs, Michelle Edwards, Gary Macgillivray, Shahla Nasserasr

Theory and Applications of Graphs

A graph $G$ is \emph{strongly $i$-bicritical} if it has independent domination number $i(G) \geq 3$, and $i(G - \{x, y\}) = i(G) - 2$ whenever $x$ and $y$ are two non-adjacent vertices of $G$. We describe five constructions of strongly $i$-bicritical graphs. For four of them, necessary and sufficient conditions for the graph produced by the construction to be strongly $i$-bicritical are given. The strongly $i$-bicritical graphs with independent domination number $i(G) = 3$ are characterized, and it is shown that the strongly $i$-bicritical graphs with independent domination number $i(G) \geq 5$ may be hard to characterize. It is shown …

Recent Studies On The Super Edge-Magic Deficiency Of Graphs, Rikio Ichishima, Susana C. Lopez, Francesc Muntaner, Yukio Takahashi

Theory and Applications of Graphs

A graph $G$ is called edge-magic if there exists a bijective function $f:V\left(G\right) \cup E\left(G\right)\rightarrow \left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert +\left\vert E\left(G\right) \right\vert \right\}$ such that $f\left(u\right) + f\left(v\right) + f\left(uv\right)$ is a constant for each $uv\in E\left( G\right) $. Also, $G$ is called super edge-magic if $f\left(V \left(G\right)\right) =\left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}$. Furthermore, the super edge-magic deficiency $ \mu_{s}\left(G\right)$ of a graph $G$ is defined to be either the smallest nonnegative integer $n$ with the property that $G \cup nK_{1}$ is super edge-magic or $+ \infty$ if there exists no such …

A Survey Of Maximal K-Degenerate Graphs And K-Trees, Allan Bickle

Theory and Applications of Graphs

This article surveys results on maximal $k$-degenerate graphs, $k$-trees,

and related classes including simple $k$-trees, $k$-paths, maximal

outerplanar graphs, and Apollonian networks. These graphs are important

in many problems in graph theory and computer science. Types of results

surveyed include structural characterizations, enumeration, degree

sets and sequences, chromatic polynomials, algorithms, and related

extremal problems.

Difference Of Facial Achromatic Numbers Between Two Triangular Embeddings Of A Graph, Kengo Enami, Yumiko Ohno

Theory and Applications of Graphs

A facial $3$-complete $k$-coloring of a triangulation $G$ on a surface is a vertex $k$-coloring such that every triple of $k$-colors appears on the boundary of some face of $G$. The facial $3$-achromatic number $\psi_3(G)$ of $G$ is the maximum integer $k$ such that $G$ has a facial $3$-complete $k$-coloring. This notion is an expansion of the complete coloring, that is, a proper vertex coloring of a graph such that every pair of colors appears on the ends of some edge.

For two triangulations $G$ and $G'$ on a surface, $\psi_3(G)$ may not be equal to $\psi_3(G')$ even if $G$ …

The Ricci Curvature On Simplicial Complexes, Taiki Yamada

Theory and Applications of Graphs

We define the Ricci curvature on simplicial complexes modifying the definition of the Ricci curvature on graphs, and prove upper and lower bounds of the Ricci curvature. These properties are generalizations of previous studies. Moreover, we obtain an estimate of the eigenvalues of the Laplacian on simplicial complexes by the Ricci curvature.

Toughness Of Recursively Partitionable Graphs, Calum Buchanan, Brandon Du Preez, K. E. Perry, Puck Rombach

Theory and Applications of Graphs

A simple graph G = (V,E) on n vertices is said to be recursively partitionable (RP) if G ≃ K1, or if G is connected and satisfies the following recursive property: for every integer partition a₁, a₂, . . . , a_k of n, there is a partition {A₁,A₂, . . . ,A_k} of V such that each |A_i| = a_i, and each induced subgraph G[A_i] is RP (1 ≤ i ≤ k). We show that if S is a …

Wiener Index In Graphs Given Girth, Minimum, And Maximum Degrees, Fadekemi J. Osaye, Liliek Susilowati, Alex S. Alochukwu, Cadavious Jones

Theory and Applications of Graphs

Let $G$ be a connected graph of order $n$. The Wiener index $W(G)$ of $G$ is the sum of the distances between all unordered pairs of vertices of $G$. The well-known upper bound $\big( \frac{n}{\delta+1}+2\big) {n \choose 2}$ on the Wiener index of a graph of order $n$ and minimum degree $\delta$ by Kouider and Winkler \cite{Kouider} was improved significantly by Alochukwu and Dankelmann \cite{Alex} for graphs containing a vertex of large degree $\Delta$ to $W(G) \leq {n-\Delta+\delta \choose 2} \big( \frac{n+2\Delta}{\delta+1}+4 \big)$. In this paper, we give upper bounds on the Wiener index of $G$ in terms of order …

On The Hardness Of The Balanced Connected Subgraph Problem For Families Of Regular Graphs, Harsharaj Pathak

Theory and Applications of Graphs

The Balanced Connected Subgraph problem (BCS) was introduced by Bhore et al. In the BCS problem we are given a vertex-colored graph G = (V, E) where each vertex is colored “red” or “blue”. The goal is to find a maximum cardinality induced connected subgraph H of G such that H contains an equal number of red and blue vertices. This problem is known to be NP-hard for general graphs as well as many special classes of graphs. In this work we explore the time complexity of the BCS problem in case of regular graphs. We prove that the BCS …

On Nowhere Zero 4-Flows In Regular Matroids, Xiaofeng Wang, Taoye Zhang, Ju Zhou

Theory and Applications of Graphs

Walton and Welsh proved that if a co-loopless regular matroid M does not have a minor in {M(K(3,3)),M^∗(K5)}, then M admits a nowhere zero 4-flow. Lai, Li and Poon proved that if M does not have a minor in {M(K5),M^∗(K5)}, then M admits a nowhere zero 4-flow. We prove that if a co-loopless regular matroid M does not have a minor in {M((P10)_¯3 ),M^∗(K5)}, then M admits a nowhere zero 4-flow where (P10)_¯3 is the graph obtained from the Petersen graph P₁₀by contracting 3 edges of a perfect matching. As …

The Gamma-Signless Laplacian Adjacency Matrix Of Mixed Graphs, Omar Alomari, Mohammad Abudayah, Manal Ghanem

Theory and Applications of Graphs

The α-Hermitian adjacency matrix H_α of a mixed graph X has been recently introduced. It is a generalization of the adjacency matrix of unoriented graphs. In this paper, we consider a special case of the complex number α. This enables us to define an incidence matrix of mixed graphs. Consequently, we define a generalization of line graphs as well as a generalization of the signless Laplacian adjacency matrix of graphs. We then study the spectral properties of the gamma-signless Laplacian adjacency matrix of a mixed graph. Lastly, we characterize when the signless Laplacian adjacency matrix of …

Bounds For The Augmented Zagreb Index, Ren Qingcuo, Li Wen, Suonan Renqian, Yang Chenxu

Theory and Applications of Graphs

The augmented Zagreb index (AZI for short) of a graph G, introduced by Furtula et al. in 2010, is defined as AZI(G)= Σ v_iv_j ∈ E(G)} (d(v_i)d(v_j)} {d(v_i)+d(v_j)-2)³, where E(G) is the edge set of G, and d(v_i) denotes the degree of the vertex v_i. In this paper, we give some new bounds on general connected graphs, molecular trees and triangle-free graphs.

New Diagonal Graph Ramsey Numbers Of Unicyclic Graphs, Richard M. Low, Ardak Kapbasov

Theory and Applications of Graphs

Grossman conjectured that R(G, G) = 2 ⋅ |V(G)| - 1, for all simple connected unicyclic graphs G of odd girth and |V(G)| ≥ 4. In this note, we prove his conjecture for various classes of G containing a triangle. In addition, new diagonal graph Ramsey numbers are calculated for some classes of simple connected unicyclic graphs of even girth.

Ts-Reconfiguration Of K-Path Vertex Covers In Caterpillars For K \Geq 4, Duc A. Hoang

Theory and Applications of Graphs

A k-path vertex cover (k-PVC) of a graph G is a vertex subset I such that each path on k vertices in G contains at least one member of I. Imagine that a token is placed on each vertex of a k-PVC. Given two k-PVCs I, J of a graph G, thek-Path Vertex Cover Reconfiguration (k-PVCR)} under Token Sliding (TS) problem asks if there is a sequence of k-PVCs between I and J where each intermediate member is obtained from its predecessor by sliding a token from some …

Ramsey Numbers For Connected 2-Colorings Of Complete Graphs, Mark Budden

Theory and Applications of Graphs

In 1978, David Sumner introduced a variation of Ramsey numbers by restricting to 2-colorings in which the subgraphs spanned by edges in each color are connected. This paper continues the study of connected Ramsey numbers, including the evaluation of several cases of trees versus complete graphs.

Optimal Orientations Of Vertex-Multiplications Of Trees With Diameter 4, Willie Han Wah Wong, Eng Guan Tay

Theory and Applications of Graphs

Koh and Tay proved a fundamental classification of G vertex-multiplications into three classes ζ₀, ζ₁ and ζ₂. They also showed that any vertex-multiplication of a tree with diameter at least 3 does not belong to the class ζ₂. Of interest, G vertex-multiplications are extensions of complete n-partite graphs and Gutin characterised complete bipartite graphs with orientation number 3 (or 4 resp.) via an ingenious use of Sperner's theorem. In this paper, we investigate vertex-multiplications of trees with diameter 4 in ζ₀ (or ζ₁) and exhibit its intricate connections with …

Outer Independent Double Italian Domination Of Some Graph Products, Rouhollah Jalaei, Doost Ali Mojdeh

Theory and Applications of Graphs

An outer independent double Italian dominating function on a graph G is a function f:V(G) →{0,1,2,3} for which each vertex x ∈ V(G) with {f(x)∈ {0,1} then Σ_{y ∈ N[x]}f(y) ⩾ 3 and vertices assigned 0 under f are independent. The outer independent double Italian domination number γ_oidI(G) is the minimum weight of an outer independent double Italian dominating function of graph G. In this work, we present some contributions to the study of outer independent double Italian domination of three graph products. We characterize the Cartesian product, lexicographic product and direct product of custom …

Counting Power Domination Sets In Complete M-Ary Trees, Hays Whitlatch, Katharine Shultis, Olivia Ramirez, Michele Ortiz, Sviatlana Kniahnitskaya

Theory and Applications of Graphs

Motivated by the question of computing the probability of successful power domination by placing k monitors uniformly at random, in this paper we give a recursive formula to count the number of power domination sets of size k in a labeled complete m-ary tree. As a corollary we show that the desired probability can be computed in exponential with linear exponent time.

Hs-Integral And Eisenstein Integral Mixed Circulant Graphs, Monu Kadyan, Bikash Bhattacharjya

Theory and Applications of Graphs

A mixed graph is called second kind hermitian integral (HS-integral) if the eigenvalues of its Hermitian-adjacency matrix of the second kind are integers. A mixed graph is called Eisenstein integral if the eigenvalues of its (0, 1)-adjacency matrix are Eisenstein integers. We characterize the set S for which a mixed circulant graph Circ(Z_n, S) is HS-integral. We also show that a mixed circulant graph is Eisenstein integral if and only if it is HS-integral. Further, we express the eigenvalues and the HS-eigenvalues of unitary oriented circulant graphs in terms of generalized Möbius function.

On Rainbow Cycles And Proper Edge Colorings Of Generalized Polygons, Matt Noble

Theory and Applications of Graphs

An edge coloring of a simple graph G is said to be proper rainbow-cycle-forbidding (PRCF, for short) if no two incident edges receive the same color and for any cycle in G, at least two edges of that cycle receive the same color. A graph G is defined to be PRCF-good if it admits a PRCF edge coloring, and G is deemed PRCF-bad otherwise. In recent work, Hoffman, et al. study PRCF edge colorings and find many examples of PRCF-bad graphs having girth less than or equal to 4. They then ask whether such graphs exist having girth greater than …

On The Uniqueness Of Continuation Of A Partially Defined Metric, Evgeniy Petrov

Theory and Applications of Graphs

The problem of continuation of a partially defined metric can be efficiently studied using graph theory. Let G=G(V,E) be an undirected graph with the set of vertices V and the set of edges E. A necessary and sufficient condition under which the weight w : E → R⁺ on the graph G has a unique continuation to a metric d : V x V → R⁺ is found.

Path-Stick Solitaire On Graphs, Jan-Hendrik De Wiljes, Martin Kreh

Theory and Applications of Graphs

In 2011, Beeler and Hoilman generalised the game of peg solitaire to arbitrary connected graphs. Since then, peg solitaire and related games have been considered on many graph classes. In this paper, we introduce a variant of the game peg solitaire, called path-stick solitaire, which is played with sticks in edges instead of pegs in vertices. We prove several analogues to peg solitaire results for that game, mainly regarding different graph classes. Furthermore, we characterise, with very few exceptions, path-stick-solvable joins of graphs and provide some possible future research questions.

Alpha Labeling Of Amalgamated Cycles, Christian Barrientos

Theory and Applications of Graphs

A graceful labeling of a bipartite graph is an α-labeling if it has the property that the labels assigned to the vertices of one stable set of the graph are smaller than the labels assigned to the vertices of the other stable set. A concatenation of cycles is a connected graph formed by a collection of cycles, where each cycle shares at most either two vertices or two edges with other cycles in the collection. In this work we investigate the existence of α-labelings for this kind of graphs, exploring the concepts of vertex amalgamation to produce a …

Radio Number Of Hamming Graphs Of Diameter 3, Jason Devito, Amanda Niedzialomski, Jennifer Warren

Theory and Applications of Graphs

For G a simple, connected graph, a vertex labeling f:V(G) → Z+ is called a radio labeling of G if it satisfies |f(u)-f(v)|≥ diam(G)+1-d(u,v) for all distinct vertices u,v ∈ V(G). The radio number of G is the minimal span over all radio labelings of G. If a bijective radio labeling onto {1,2,…|V(G)|} exists, G is called a radio graceful graph. We determine the radio number of all diameter 3 Hamming graphs and show that an infinite subset of them is radio graceful.

Restrained Reinforcement Number In Graphs, Kazhal Haghparast, Jafar Amjadi, Mustapha Chellali, Seyed Mahmoud Sheikholeslami

Theory and Applications of Graphs

A set S of vertices is a restrained dominating set of a graph G=(V,E) if every vertex in V\ S has a neighbor in S and a neighbor in V\S. The minimum cardinality of a restrained dominating set is the restrained domination number γ_r(G). In this paper we initiate the study of the restrained reinforcement number r_r(G) of a graph G defined as the cardinality of a smallest set of edges F ⊆ E( ‾G) for which γ_r(G + F) < γ_r(G), where ‾G denotes the complement graph of G. …

On The Integer-Antimagic Spectra Of Non-Hamiltonian Graphs, Wai Chee Shiu, Richard M. Low

Theory and Applications of Graphs

Let A be a nontrivial abelian group. A connected simple graph G = (V, E) is A-antimagic if there exists an edge labeling f: E(G) → A \ {0} such that the induced vertex labeling f+: V(G) → A, defined by f+(v) = Σ {f(u,v): (u, v) ∈ E(G)}, is a one-to-one map. In this paper, we analyze the group-antimagic property for Cartesian products, hexagonal nets and theta graphs.

Harmonious Labelings Via Cosets And Subcosets, Jared L. Painter, Holleigh C. Landers, Walker M. Mattox

Theory and Applications of Graphs

In [Abueida, A. and Roblee, K., More harmonious labelings of families of disjoint unions of an odd cycle and certain trees, J. Combin. Math. Combin. Comput., 115 (2020), 61-68] it is shown that the disjoint union of an odd cycle and certain paths is harmonious, and that certain starlike trees are harmonious using properties of cosets for a particular subgroup of the integers modulo m, where m is the number of edges of the graph. We expand upon these results by first exploring the numerical properties when adding values from cosets and subcosets in the integers modulo m. …

On The Total Set Chromatic Number Of Graphs, Mark Anthony C. Tolentino, Gerone Russel J. Eugenio, Mari-Jo P. Ruiz

Theory and Applications of Graphs

Given a vertex coloring c of a graph, the neighborhood color set of a vertex is defined to be the set of all of its neighbors’ colors. The coloring c is called a set coloring if any two adjacent vertices have different neighborhood color sets. The set chromatic number χ_s(G) of a graph G is the minimum number of colors required in a set coloring of G. In this work, we investigate a total analog of set colorings; that is, we study set colorings of the total graph of graphs. Given a graph G = (V, E) …

On P-Competition Graphs Of Loopless Hamiltonian Digraphs Without Symmetric Arcs And Graph Operations, Kuniharu Yokomura, Morimasa Tsuchiya

Theory and Applications of Graphs

For a digraph D, the p-competition graph C_p(D) of D is the graph satisfying the following: V(C_p(D))=V(D), for x,y ∈ V(C_p(D)), xy ∈ E(C_p(D)) if and only if there exist distinct p vertices v₁, v₂, ..., v_p ∈ V(D) such that x → v_i, y → v_i ∈ A(D) for each i=1,2, ..., p.

We show the H₁ ∪ H₂ is a p-competition graph of a loopless digraph without symmetric arcs for p ≥ 2 , where …

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 …

Total Colouring Of New Classes Of Subcubic Graphs, Sethuraman G, Velankanni Anthonymuthu

Theory and Applications of Graphs

The total chromatic number of a graph G, denoted χ”(G), is the least number of colours needed to colour the vertices and the edges of G such that no incident or adjacent elements (vertices or edges) receive the same colour. The popular Total Colouring Conjecture (TCC) posed by Behzad states that, for every simple graph G, χ”(G) ≤ Δ(G)+2. In this paper, we prove that the total chromatic number for a family of subcubic graphs called cube connected paths and also for a class of subcubic graphs having the property that the vertices are covered by independent …