Narrow Results

In [Ilyutko and Safina, Graph-links: nonrealizability, orientation, and Jones polynomial, J. Math. Sc.214(5) (2016) 632–664], the first named author defined the notion of an oriented graph-link and constructed a writhe number of a vertex of an oriented graph-link, which equals the “real” writhe number of a crossing in the realizable case. As a result the Jones polynomial was defined for oriented graph-links and the first example of a non-realizable graph-link with more than one component was found. Despite the fact that all necessary definitions were given the authors did not define the notion of linking number for graph-links. In this paper, we are eliminating this deficiency. Moreover, we classify all graph-links having a representative with less than $4$ vertices.

In this paper, we generalize virtual knot theory to multi-virtual knot theory where there are a multiplicity of virtual crossings. Each virtual crossing type can detour over the other virtual crossing types, and over classical or immersed crossings. New invariants of multi-virtual knots and links are introduced and new problems that arise are described. We show how the extensions of the Penrose coloring evaluation for trivalent plane graphs and our generalizations of this to non-planar graphs and arbitrary numbers of colors acts as a motivation for the construction of the multi-virtual theory.

We show that for any finite group $G$, there exist infinitely many simple anticommutative algebras with multiplicative bases $(𝔄,\mathcal{ℬ})$ such that the group $\mathrm{\text{Aut}}((𝔄,\mathcal{ℬ}))$ is isomorphic to $G$.

A graph $G$ is a fractional $(a,b,m)$-deleted graph if deleting any $m$ edges from $G$, the resulting subgraph still admits a fractional $[a,b]$-factor. As an exclusive graph-based parameter, isolated toughness and its variant are utilized to measure the vulnerability of networks which are modelled by graph topology structures. Early studies have shown the inherent connection between isolated toughness and the existence of fractional factors in specific settings. This paper provides a theoretical perspective on the sufficient conditions for fractional $(a,b,m)$-deleted graphs with respect to isolated toughness and its variant. The sharpness of the given isolated toughness bounds is explained by counterexamples.

Soft set theory provides a systematic approach for handling imprecision and uncertainty by categorizing elements of a set based on specific parameters. In semigraph theory, soft semigraphs utilize this approach, offering a parameterized perspective that has significantly advanced the field through effective parameter management. Building on this foundation, disemigraphs extend semigraphs by incorporating directional relationships among vertices, making them ideal for modeling scenarios where the sequence and direction of connections are crucial. In this paper, we introduce and explore the lexicographic product, and restricted lexicographic product of soft disemigraphs. We provide formal definitions, illustrative examples, and detailed proofs of several theorems to investigate the properties of these product operations.

Let $R$ be a commutative ring with identity and $I$ be an ideal of $R$. The zero-divisor graph of $R$ with respect to $I$, denoted by ${\mathrm{\Gamma }}_I(R)$, is the graph whose vertices are the set $\{x\in R\setminus I|xy\in I\mathrm{\text{for}}\mathrm{\text{some}}y\in R\setminus I\}$ with distinct vertices $x$ and $y$ are adjacent if and only if $xy\in I$. The cozero-divisor graph ${\mathrm{\Gamma }}^{\prime }(R)$ of $R$ is the graph whose vertices are precisely the non-zero, non-unit elements of $R$ and two distinct vertices $x$ and $y$ are adjacent if and only if $x\notin yR$ and $y\notin xR$. In this paper, we introduced and investigated a new generalization of the cozero-divisor graph ${\mathrm{\Gamma }}^{\prime }(R)$ of $R$ denoted by ${\mathrm{\Gamma }}_I^{″}(R)$. In fact, ${\mathrm{\Gamma }}_I^{″}(R)$ is a dual notion of ${\mathrm{\Gamma }}_I(R)$.

In this paper, we study a new graph structure, called the $directsumgraph$ on a finite-dimensional vector space. We investigate the connectivity, diameter and the completeness of ${\mathrm{\Gamma }}_{U\oplus W}(𝕍)$. We also determine the degree of each vertex in case the base field is finite. We establish some results about Eulerian and triangulation of the graph ${\mathrm{\Gamma }}_{U\oplus W}(𝕍)$. Finally, we find the domination number and independence number, size, girth, edge-connectivity, clique number and the chromatic number of ${\mathrm{\Gamma }}_{U\oplus W}(𝕍)$.

In this paper we introduce a new graph polynomial, say connectivity polynomial. Let $G$ be a simple graph of order $n$. The connectivity polynomial of $G$, denoted by ${𝒞}(G,x)$, is ${𝒞}(G,x)={\sum }_{i=0}^n{c}_i{x}^i$, where $c_0=1$ and $c_i$ (for $i\ge 1$) is the number of connected induced subgraphs of $G$ with order $i$. We investigate some properties of the connectivity polynomial. We find the connectivity polynomial of disjoint union and join of graphs. Finally, we find the coefficients of this polynomial in terms of the vertex connectivity and the order of graphs.

Graph properties’ computation is widely used in science. Some algorithms for specific graphs help us compute properties like girth, clique number, and independent number. Nevertheless, processing time would be increased by the growth of the number of graph vertices. This paper suggests machine learning methods for computing a given graph’s girth, maximum clique number, and maximum independent set number. We leveraged random graph generation methods to collect many graph instances. Next, we present 14 features used for the training and testing while classifying or predicting those properties. The experimental results on the collected dataset offer accuracies of 90.51%, 91.61%, and 99.99% for binary classification and correlation coefficients of 0.9703, 0.8757, and 0.992 for value prediction for maximum clique number, girth, and maximum independent set number, respectively.

We present an efficient algorithm which computes the set of minimal separators of a graph in O(n³) time per separator, thus gaining a factor of n² on the current best-time algorithms for this problem.

Our process is based on a new structural result, derived from the work of Kloks and Kratsch on listing all the minimal separators of a graph.

Remmel and Williamson recently defined a class of directed graphs, called filtered digraphs, and described a natural class of bijections between oriented spanning forests of these digraphs and associated classes of functions [12]. Filtered digraphs include many specialized graphs such as complete k-partite graphs. The Remmel-Williamson bijections provide explicit formulas for various multivariate generating functions for the oriented spanning forests which arise in this context. In this paper, we prove another important property of these bijections, namely, that it allows one to construct efficient algorithms for ranking and unranking spanning trees or spanning forests of filtered digraphs G. For example, we show that if G=(V,E) is a filtered digraph and SP(G) is the collection of spanning trees of G, then our algorithm requires O(|V|) operations of sum, difference, product, quotient, and comparison of numbers less than or equal |SP(G)| to rank or unrank spanning trees of G.

A k-forward numbering of a graph is a labeling of the nodes with integers such that each node has less than k neighbors whose labels are equal or larger. Distributed algorithms that reach a legitimate state, starting from any illegitimate state, are called self-stabilizing. We obtain three self-stabilizing (s-s) algorithms for finding a k-forward numbering, provided one exists. One such algorithm also finds the k-height numbering of graph, generalizing s-s algorithms by Bruell et al. [4] and Antonoiu et al. [1] for finding the center of a tree. Another k-forward numbering algorithm runs in polynomial time. The motivation of k-forward numberings is to obtain new s-s graph coloring algorithms. We use a k-forward numbering algorithm to obtain an s-s algorithm that is more general than previous coloring algorithms in the literature, and which k-colors any graph having a k-forward numbering. Special cases of the algorithm 6-color planar graphs, thus generalizing an s-s algorithm by Ghosh and Karaata [13], as well as 2-color trees and 3-color series-parallel graphs. We discuss how our s-s algorithms can be extended to the synchronous model.

In this paper, we provide complete classification of classes of bipartite graphs defined by a single forbidden induced bipartite subgraph with respect to bounded/unbounded clique-width.

Two mobile agents, starting at arbitrary, possibly different times from arbitrary nodes of an unknown network, have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. Agents have different labels which are positive integers. Each agent knows its own label, but not the label of the other agent. In traditional formulations of the rendezvous problem, meeting is accomplished when the agents get to the same node in the same round. We want to achieve a more demanding goal, called rendezvous with detection: agents must become aware that the meeting is accomplished, simultaneously declare this and stop. This awareness depends on how an agent can communicate to the other agent its presence at a node. We use two variations of the arguably weakest model of communication, called the beeping model, introduced in [8]. In each round an agent can either listen or beep. In the local beeping model, an agent hears a beep in a round if it listens in this round and if the other agent is at the same node and beeps. In the global beeping model, an agent hears a loud beep in a round if it listens in this round and if the other agent is at the same node and beeps, and it hears a soft beep in a round if it listens in this round and if the other agent is at some other node and beeps.

We first present a deterministic algorithm of rendezvous with detection working, even for the local beeping model, in an arbitrary unknown network in time polynomial in the size of the network and in the length of the smaller label (i.e., in the logarithm of this label). However, in this algorithm, agents spend a lot of energy: the number of moves that an agent must make, is proportional to the time of rendezvous. It is thus natural to ask if bounded-energy agents, i.e., agents that can make at most c moves, for some integer c, can always achieve rendezvous with detection as well. This is impossible for some networks of unbounded size. Hence we rephrase the question: Can bounded-energy agents always achieve rendezvous with detection in bounded-size networks? We prove that the answer to this question is positive, even in the local beeping model but, perhaps surprisingly, this ability comes at a steep price of time: the meeting time of bounded-energy agents is exponentially larger than that of unrestricted agents. By contrast, we show an algorithm for rendezvous with detection in the global beeping model that works for bounded-energy agents (in bounded-size networks) as fast as for unrestricted agents.

The additional closeness is a very important characteristic of graphs. It measures the maximal closeness of a graph after adding a new link and it is an indication of the growth potential of graphs’ closeness. Most of the time calculating the additional closeness requires solving nontrivial optimization problems. In this article, the additional closenesses of cycles, gear, and some other graphs are calculated. Bounds for additional closeness of graphs are discussed.

Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that the k paths connecting r and any vertex v in the k trees are internally disjoint. In this paper we give a linear-time algorithm to find four independent spanning trees in a 4-connected planar graph.

Suppose that $M$ is a product of compact Riemann surfaces $M_1$,$M_2$, i.e. $(M,ḡ)=(M_1\times M_2,{ḡ}_1\oplus {ḡ}_2)$, and $\mathrm{\Gamma }(f)$ is a graph in $M$ of a strictly area dereasing map $f:M_1\to M_2$. Let $(M,ḡ(t))$ evolve along the Kähler–Ricci flow, and ${\mathrm{\Gamma }}_t(f)$ in $(M,ḡ(t))$ evolve along the mean curvature flow. We show that ${\mathrm{\Gamma }}_t(f)$ remains to be a graph of a strictly area decreasing map along the Kähler–Ricci mean curvature flow and exists for all time. In the positive scalar curvature case, we prove the convergence of the flow and the curvature decay along the flow at infinity.

A network was characterized by its viscoelastic properties. The viscoelastic property indicates the deformations or changes in the shape and in the internal structure during the evolution of a network. The change in the direction of motion was taken as elastic deformation and the change in the vertical direction as viscous deformation. These deformations were related to the change of geometry of internal structure and of shape. Thus it was possible to characterize a network by its storage and loss moduli. The change of the structure of a network during its evolution changes also its entropy. However entropy depends on the number of microstates of an already existing framework. As examples, two different systems (i) New York Stock Exchange and (ii) a melody were studied for their viscoelastic properties. The change of viscous property was compared with the change of different types of entropies such as configurational entropy, crossing entropy, and topological entropy. This last entropy was introduced and explained in the text. It was found out that there is no direct correspondence between the increase of entropy and the increase of viscous property of a network although they sometimes correlate with each other.

Terrorist network may be defined as collection of suspected terrorist nodes which may function in disguise towards accomplishing a terrorist activity. They use extensive communication channel for sharing crucial information. Terrorist network analysis is highly efficacious for intelligence analysis and deriving useful conclusions from available data. Computer Science and Network analysis act as pertinent fields for the study and graphical interpretation of these networks. In this paper, we examine the 26/11 Mumbai attack terrorist network dataset and employ the ELECTRE method for identification of key node in the terrorist network. ELECTRE is an effective multi-criteria decision-making model. It provides a framework for structuring a decision problem integrates the quantitative and qualitative factors of the problem and facilitates easy computation. From the 26/11 Mumbai attack dataset of terrorist network, we have determined that out of several terrorists in the network “Wassi” was the momentous and mastermind of all. The proposed work also demonstrates improvement of result in terms of concurrence, generalization accuracy and genuineness. Based on the solution of ELECTRE framework, it is resolved that the obtained (terrorist) nodes will step up the work of law enforcement agencies and enable them to confine their focus on important members of the terrorist network. Identification of key terrorist is highly important for developing long-term strategies to counter forthcoming terrorist attacks. It can be better implemented during the development of smart city especially for India.

A hierarchical abstraction scheme based on node contraction and two related similarity measures for graphs with unique node labels are proposed in this paper. The contraction scheme reduces the number of nodes in a graph and leads to a speed-up in the computation of graph similarity. Theoretical properties of the new graph similarity measures are derived and experimentally verified. A potential application of the proposed graph abstraction scheme in the domain of computer network monitoring is discussed.