Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- $k$-path vertex covers (1)
- (Outer independent) double Italian domination number (1)
- Agumented Zagreb index; molecular trees; Triangle-free graph (1)
- Antichains (1)
- Average distance (1)
-
- Cartesian product (1)
- Caterpillars (1)
- Combinatorics (1)
- Complete coloring (1)
- Computational Complexity (1)
- Connectivity (1)
- Continuations of metrics (1)
- Cross-intersecting (1)
- Cycle covers (1)
- Diagonal Ramsey numbers (1)
- Direct product (1)
- Edge coloring (1)
- Eigenvalue of Laplacian (1)
- Eisenstein integer (1)
- Excluded-minors (1)
- Facial complete coloring (1)
- Generalized polygon (1)
- Girth (1)
- Graph Ramsey theory (1)
- Graph Theory (1)
- HS-integral mixed graph (1)
- Independence number (1)
- Integral graphs (1)
- Lexicographic product (1)
- Maximum degree (1)
Articles 1 - 17 of 17
Full-Text Articles in Physical Sciences and Mathematics
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 …