Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Cartesian product (4)
- Dominating set (3)
- Domination number (3)
- Edge-coloring (3)
- Graphical degree sequence (3)
-
- Independent set (3)
- Maximum degree (3)
- Trees (3)
- Triangulation (3)
- Vizing's conjecture (3)
- $\alpha$-labeling (2)
- Cartesian product of graphs (2)
- Co-NP (2)
- Complete multipartite graph (2)
- Computational complexity (2)
- Connectivity (2)
- Diameter (2)
- Directed graph (2)
- Distance (2)
- Domination (2)
- Edge coloring (2)
- Facial complete coloring (2)
- Girth (2)
- Graph theory (2)
- Graphical partition (2)
- Integer-antimagic graph (2)
- Interconnection Networks (2)
- Inverse domination (2)
- K-forcing number (2)
- Laplacian spectrum (2)
Articles 1 - 30 of 121
Full-Text Articles in Entire DC Network
Approval Gap Of Weighted K-Majority Tournaments, Jeremy Coste, Breeann Flesch, Joshua D. Laison, Erin Mcnicholas, Dane Miyata
Approval Gap Of Weighted K-Majority Tournaments, Jeremy Coste, Breeann Flesch, Joshua D. Laison, Erin Mcnicholas, Dane Miyata
Theory and Applications of Graphs
A $k$-majority tournament $T$ on a finite set of vertices $V$ is defined by a set of $2k-1$ linear orders on $V$, with an edge $u \to v$ in $T$ if $u>v$ in a majority of the linear orders. We think of the linear orders as voter preferences and the vertices of $T$ as candidates, with an edge $u \to v$ in $T$ if a majority of voters prefer candidate $u$ to candidate $v$. In this paper we introduce weighted $k$-majority tournaments, with each edge $u \to v$ weighted by the number of voters preferring $u$.
We define the …
Strongly I-Bicritical Graphs, Michelle Edwards, Gary Macgillivray, Shahla Nasserasr
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
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
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
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
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
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 a1, a2, . . . , ak of n, there is a partition {A1,A2, . . . ,Ak} of V such that each |Ai| = ai, and each induced subgraph G[Ai] 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
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
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
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 P10by contracting 3 edges of a perfect matching. As …
The Gamma-Signless Laplacian Adjacency Matrix Of Mixed Graphs, Omar Alomari, Mohammad Abudayah, Manal Ghanem
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
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)= Σ vivj ∈ E(G)} (d(vi)d(vj)} {d(vi)+d(vj)-2)3, where E(G) is the edge set of G, and d(vi) denotes the degree of the vertex vi. 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
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
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
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
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 ζ0, ζ1 and ζ2. They also showed that any vertex-multiplication of a tree with diameter at least 3 does not belong to the class ζ2. 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 ζ0 (or ζ1) and exhibit its intricate connections with …
Outer Independent Double Italian Domination Of Some Graph Products, Rouhollah Jalaei, Doost Ali Mojdeh
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
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
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(Zn, 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 The Uniqueness Of Continuation Of A Partially Defined Metric, Evgeniy Petrov
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.
On Rainbow Cycles And Proper Edge Colorings Of Generalized Polygons, Matt Noble
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 …
Path-Stick Solitaire On Graphs, Jan-Hendrik De Wiljes, Martin Kreh
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
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
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.
On The Integer-Antimagic Spectra Of Non-Hamiltonian Graphs, Wai Chee Shiu, Richard M. Low
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.
Restrained Reinforcement Number In Graphs, Kazhal Haghparast, Jafar Amjadi, Mustapha Chellali, Seyed Mahmoud Sheikholeslami
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 rr(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 P-Competition Graphs Of Loopless Hamiltonian Digraphs Without Symmetric Arcs And Graph Operations, Kuniharu Yokomura, Morimasa Tsuchiya
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 Cp(D) of D is the graph satisfying the following: V(Cp(D))=V(D), for x,y ∈ V(Cp(D)), xy ∈ E(Cp(D)) if and only if there exist distinct p vertices v1, v2, ..., vp ∈ V(D) such that x → vi, y → vi ∈ A(D) for each i=1,2, ..., p.
We show the H1 ∪ H2 is a p-competition graph of a loopless digraph without symmetric arcs for p ≥ 2 , where …
Harmonious Labelings Via Cosets And Subcosets, Jared L. Painter, Holleigh C. Landers, Walker M. Mattox
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. …
Geodesic Bipancyclicity Of The Cartesian Product Of Graphs, Amruta V. Shinde, Y.M. Borse
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 …
On The Total Set Chromatic Number Of Graphs, Mark Anthony C. Tolentino, Gerone Russel J. Eugenio, Mari-Jo P. Ruiz
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) …