Electronic Journal of Graph Theory and Applications (EJGTA)

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 …

A proper vertex-coloring of a graph G is called distinguishing, if the only automorphism preserving the colors is the identity. The minimum number of colors for such a coloring is denoted by χ D (G) . We say a graph G is uniquely proper distinguishing colorable (UPDC, for short) if and only if there exists only one partition of V(G) into χ D (G) independent sets such that the identity is the only…

An important question in the study of quasi-perfect codes is whether such codes can be constructed for all possible lengths n . In this paper, we address this question for specific values of n . First, we investigate the existence of quasi-perfect codes in the Cartesian product of a graph G and a path (or cycle), assuming that G admits a perfect code. Second, we explore quasi-perfect codes in the…

This paper establishes explicit combinatorial characterizations for fundamental structural properties of Cayley signed graphs defined on finite Abelian groups. We derive precise necessary and sufficient conditions for balance, clusterability, and sign-compatibility of both these graphs and their line graphs. By leveraging the prime factorization structure of the underlying group G , we prove that…

Let G be a finite non-abelian group. The centralizer graph of G is a simple undirected graph Γcent(G) , whose vertices are the proper centralizers of G and two vertices are adjacent if and only if their cardinalities are identical. The complement of the centralizer graph is called the co-centralizer graph. In this paper, we investigate the adjacency and (signless) Laplacian spectra of centralizer…