graph-theory

In this paper, we determine the edge metric dimension of the comb product of a cycle graph and a simple graph containing a dominant vertex. This result generalizes previous findings on the edge metric dimension of the comb product of a cycle and a complete graph. We show that the edge metric dimension of C n ▷ D , where D is a simple graph with a dominant vertex, equals the product of the order o…

The matching book embedding of a graph G is an embedding of G with the vertices on the spine, and each edge within a single page so that the edges on each page do not intersect and the degree of vertices on each page is at most one. The matching book thickness of G is the minimum number of pages in a matching book embedding of G, denoted by mbt(G). In this paper, the exact matching book thickness…

The capability of one architecture to simulate another serves as the foundation for network comparison, with embedding playing a key role in analyzing these simulations. In architectural simulation, graph embedding is one of the most powerful techniques for executing parallel algorithms and modeling diverse interconnection networks. In our earlier work, we listed an open problem that the determin…

For a graph G = (V, E) embedded in the projective plane, let F(G) denote the set of faces of G. Then, G is called a Cₙ-face-magic projective graph if there exists a bijection f: V(G) → {1, 2, …, |V(G)|} such that for any F ∈ F(G) with F ≅ Cₙ, the sum of all the vertex labels around Cₙ is a constant S. We consider the m × n grid graph, denoted by P m,n , embedded in the projective plane in the nat…

This paper presents three main results concerning the coloring of discrete d-pseudomanifolds: (1) the general chromatic bounds d+1 ≤ X(K) ≤ 2d+2 for any d-pseudomanifold K; (2) an improved bound X(K) ≤ 2d+1 for a d-pseudomanifold expressible as a join K = S k + K', where S k is a cyclic k-sphere and K' is a subpseudomanifold; (3) the optimal bound X(K) ≤ ⌈3(d+1)/2⌉, where ⌈-⌉ is a ceiling functio…

We study decompositions and packings in truncated triangulations G T△ obtained from simple connected plane graphs G with minimum degree two. We show G T△ is a 3-connected cubic planar graph with at least 2|E(G)|² - 2|E(G)| + 1 perfect matchings, a Λ-factor, and can be decomposed into a union of C₆'s and K₂'s if G is bipartite. Additionally, we show that G T△ is hamiltonian if G is bipartite with …

Dénés established the connection between labeled trees in Graph Theory and factorizations of cyclic permutations by means of transpositions. In this paper, we introduce the notion of an inversion-transposition, which has both the properties of an inversion and a transposition. For a cyclic permutation, we define the graph associated with each minimal representation using only inversion-transposit…

Graphs in which the absolute difference between the degrees of any two adjacent vertices is exactly one, are called stepwise irregular (SI) graphs. We establish several properties of SI graphs. In particular, we show that SI graphs of different order and cyclomatic numbers can be constructed from an SI graph with a vertex of degree 1 or 2. Necessary conditions and sufficient conditions for a degr…

We improve several previously known bounds of the connected-pseudoachromatic index of complete graphs. We apply a Rank Genetic Algorithm to find experimental solutions above the known lower bounds and then we obtain an approximation of the upper bound to verify and compare to the empirically obtained results.

In this paper we introduce an intersection graph of a graph G , with vertex set the minimum edge-cuts of G . We find the minimum cut-set graphs of some well-known families of graphs and study the mincut graph as a graph operator. In doing so we follow the research programme on graph operators, as introduced by Prisner in the 1995 monograph "Graph Dynamics". Thus we ask and attempt to answer quest…

A signed graph Σ is the ordered pair (G,σ), where G=(V,E) is a finite simple graph, called the underlying graph, and σ: E(G) → {+1, -1} is a sign function or a signature of Σ. Let (K_n,σ) be a complete signed graph with n vertices. In this paper, we give a complete description of the adjacency, Laplacian and net Laplacian spectrum of a complete signed graph (K_n,σ) whenever its negative edges ind…

In this paper we present enumerative results for Stirling numbers of the first kind for two graph products, the matched product and the m-star, using the combinatorial model of rearrangements. The kth Stirling number of the first kind for a simple graph G counts the number of ways to decompose G into exactly k vertex-disjoint cycles, including single vertices as 1-cycles, single edges as 2-cycles…

This paper presents a possible link between Cages and Expander Graphs by introducing three interconnected variants of the Bermond and Bollobás Conjecture, originally formulated in 1981 within the context of the Degree/Diameter Problem. We adapt these conjectures to cages, with the most robust variant posed as follows: Does there exist a constant c such that for every pair of parameters k,g there …

The Tree Packing Conjecture of Gyárfás states that for any set of n-1 trees T = {T₁, T₂, …, T n-1 }, where T i has i edges, T can be packed into K n . We define a family of trees called two-spiders that are almost stars, and show that packings of K n with two-spiders can be constructed by exchanging edges of known packings. We prove that if each tree T i ∈ T is a two-spider and has at most α i tw…

We develop a theory of ×-homotopy, fundamental groupoids and covering spaces that applies to non-simple graphs, generalizing existing results for simple graphs. We prove that ×-homotopies from finite graphs can be decomposed into moves that adjust at most one vertex at a time, generalizing the spider lemma of Chih & Scull (2021). We define a notion of homotopy covering map and develop a theory of…

Consider a graph G = (V(G), E(G)) , where V(G) is a nonempty set of vertices and E(G) is a set of edges. Let Z n be the group of integers modulo n , and let k be a positive integer. A modular irregular labeling of a graph G of order n is a k -edge labeling ϕ : E(G) → {1, 2, … , k} , such that an induced weight function wt ϕ : V(G) → Z n is bijective. The weight function is defined as follows: wt …

Given a cardinal $\kappa > 2$, is there a triangle-free vertex-transitive graph $G=(V,E)$ with chromatic number $\chi(G) = \kappa$?

IntroductionRadio labeling of graphs extends the channel assignment problem by assigning non-negative integers to vertices of a connected graph G such that |h(℘)−h(𝓆)|≥diam(ℊ)+1−d(℘, 𝓆). The objective is to minimize the span, leading to the radio number rn(G).MethodsWe consider a class of outerplanar graphs with vertex set {u1, v1, x1, …, xn, y1, …, yn} and a structured edge set combining path an…

Number Trail is a path-filling puzzle built entirely in plain HTML, CSS, and a single JavaScript module with no frameworks and no bundler. The player draws one continuous path that visits every cell of a square grid exactly once, touching numbered clue cells in ascending order. You can play the game here: The core constraint is a Hamiltonian path problem: find a path through a graph that visits e…

I came across the graph of: $$\cos{x}>\cos{y}$$ and was shocked by the fact that the graph turned up like a tilted chess-board. I am interested in bringing up discussions and other curves(...