Jun 2026· Journal of Physics, Conference Series· Vol 3268, pp. 012005· 0 citations· 18 references
Physics
Abstract
Let G be a finite group. We introduce a new graph definition, called the pseudo A4-graph, as an extension of the classical A4-graph. The pseudo A4-graph of G or PA4-graph is a simple graph ΓG whose vertices are elements of G, and two distinct vertices a and b are joined by an edge if and only if ab−1 = ba−1. This paper presents the formulas for certain graph invariants such as the number of edges, diameter, total degree, chromatic number, clique number, independence number, domination number, matching number, and graph energy. The method involves constructing the A4-graphs of dihedral groups, analyzing their structure, and systematically computing graph invariants through algebraic reasoning and combinatorial techniques to establish fundamental properties and relationships. One of the results in this paper comply with the well-known fact that the energy of a graph is always an even integer.
Akbari, Elphick, Kumar, Pragada and Tang [Discrete Math. 349 (2026) 114953] conjectured that for every connected graph G, the line graph of G has at most one more positive than negative adjacency eigenvalue; equivalently, the signature of a connected line graph is at most 1. We refute the conjecture with two independently found counterexamples: a 14-vertex cactus consisting of two pentagons attached by bridges to adjacent vertices of a square, whose line graph has inertia (9,0,7) by an exact characteristic-polynomial certificate, and a 48-vertex triangle-free graph found by simulated annealing and verified in exact rational arithmetic. Indeed, chaining copies of the 14-vertex graph yields connected graphs on 14k vertices whose line graphs have signature k+1 for every k>= 1. The signature of connected line graphs is therefore unbounded, and no constant-bound repair of the conjecture is possible.
Sharma and Panda recently proved that every bipartite graph with a perfect matching has property (P); that is, it admits a non-singular real symmetric matrix with support graph G for which every vertex is a P -vertex. In this paper, we extend their result from bipartite graphs to arbitrary graphs. To this end, we introduce the notion of a P - vertex covering and define the P -vertex covering number p(G) as the minimum number of non-singular matrices in S(G) needed so that every vertex of G is a P -vertex of at least one of them. Given a maximal matching of G, we partition the vertex set into the vertices saturated by the matching and the remaining vertices, which necessarily form an independent set. We then construct separate matrices covering these two classes of vertices. We use the Implicit Function Theorem as a perturbation tool to establish the desired result.
A graph category is a category with a set of graphs or similar structures (such as, directed graphs, signed graphs, etc.) playing the role of objects, and an appropriate notion of homomorphism playing the role of morphisms. The characterization of multiplicative objects are important open problems in categories of undirected and directed graphs. While the recent disproving of the Hedetniemi's conjecture due to Shitov (Ann. Math. 2019), which claimed that all complete graphs are multiplicative, provided a breakthrough in the study of multiplicative undirected graphs, the characterization of multiplicative undirected graphs remains known only for cycles, circular cliques $K_{{n/k}}$ where ${n/k} \in (2,4]$, complete graphs, and graphs whose each edge is part of at most one $4$-cycle. Similarly, whether a given directed graph is multiplicative or not is known only for some oriented paths, oriented cycles, and transitive tournaments. We study multiplicative graphs in the category of directed graphs where pushable homomorphism plays the role of morphism. We provide full multiplicativity characterization for directed bipartite graphs, oriented cycles, and transitive tournaments. As a consequence we find new (infinite) classes of non-multiplicative directed graphs in the usual directed graphs category. We also resolve an open question posed by Das \textit{et al.} (CALDAM 2026) related to the existence of exponential directed graphs with respect to pushable homomorphisms, and use our solution as a tool for our proofs.
S. Das, Moritz Muhlenthaler, Sagnik Sen et al.· 0 citations
In this paper, we construct a class of infinite graphs, called substitution graphs. The vertex set consists of all finite words over a finite alphabet. A directed graph is formed by adding vertical edges connecting each word to its children and horizontal edges defined recursively by two finite directed graphs G and J: edges among vertices with the same parent follow G, while edges between vertices whose parents are horizontally linked follow J. The substitution graph is defined as its underlying graph. Substitution graphs provide a purely combinatorial model of self-similar structures, independent of any underlying geometric structure. Furthermore, we establish a necessary and sufficient condition for substitution graphs to be hyperbolic, formulated in terms of the vanishing of path matrices associated with sufficiently long shortest horizontal paths. Based on this characterization, we further derive several conditions that are either necessary or sufficient for hyperbolicity, depending only on the generators G and J.
Qingcheng Zeng, Cheng Zeng, Yumei Xue et al.· 0 citations
We prove that a graph $G$ is quasi-planar - i.e. quasi-isometric to a planar graph - if and only if it can be obtained by iterating the following two operations a bounded number of times: a) subdividing each edge into a path of bounded length, and b) taking the intersection graph of a family of connected subgraphs covering $G$. This applies both to infinite graphs, and to families of finite graphs with uniform constants. The backward implication relies on, and generalises, a deep result of Davies, partly proved independently by Chang, Conroy, Tan&Zheng, saying that every string graph is quasi-planar. The forward implication requires new ideas. As a byproduct of our proofs, we deduce that every contraction minor of a quasi-planar graph is quasi-planar. Moreover, if $G$ admits a tree-decomposition with adhesions of bounded diameter and quasi-planar induced bags, then $G$ is itself quasi-planar. Our results apply to other graph classes as well, and we offer various tools for understanding quasi-isometries as well as bi-Lipschitz equivalences between graphs.
For a graph and a graph family , let denote the maximum number of copies of in an ‐free ‐vertex graph. Let . Bai, Tompkins, and Well conjectured that is attained if and each block of the graph is a . In this paper, we determine the exact value of and the extremal graphs for all . The novelty of our proof is to give a proper partition of the set of triangles in an extremal graph. On the basis of this partition, we obtain the partition of the edge set and thus the structure of an extremal graph. Our new method can also be applied to obtain some meaningful results in other settings.
Xiaojun Zhao, Yuejian Peng· Journal of Graph Theory· 1 citation