Search

A new kind of bipartite graph is defined in this paper. The work is motivated mainly from a graph introduced by Al-Kaseasbeh and Erfanian [A bipartite graph associated to elements and cosets of subgroups of a finite group, AIMS Math. 6(10) (2021) 10395–10404] and partially from the undirected power graph of a group and from the inclusion graph. For a nontrivial group G, we define a simple undirected bipartite graph Γ(G) with the vertex set V (Γ(G)) = A ∪ B, where A is the set of all elements of the group G and B is the set of all subgroups H of G such that H≠{e} and two vertices a ∈ A and H ∈ B are adjacent if and only if a2 ∈ H. Here, we classify all the finite groups G whose bipartite graphs Γ(G) are planar. In addition, we also classify the finite groups G such that Γ(G) is outerplanar, maximal planar, maximal outerplanar, star, tree, claw graph, respectively. The planarity of the graph Γ(G) corresponding to an infinite group G has also been investigated here. It is also observed that Γ(G) satisfies Vizing’s conjecture. [ABSTRACT FROM AUTHOR]

For a graph G , let i k (G) be the number of independent sets of size k in G. The independence polynomial I (G ; x) = ∑ k ≥ 0 i k (G) x k has been the focus of considerable research. In this paper, using the coefficients of independence polynomials, we order graphs with some given parameters. We first determine the extremal graph whose all coefficients of I (G ; x) are the largest (respectively, smallest) among all connected graphs (respectively, bipartite graphs) with given vertex cover number. Then we also derive the extremal graph whose all coefficients of I (G ; x) are the largest among all connected graphs (respectively, bipartite graphs) with given vertex dominate number. [ABSTRACT FROM AUTHOR]

In this paper, we first give some sufficient criteria for normality of monomial ideals. As applications, we show that closed neighborhood ideals of complete bipartite graphs are normal, and hence satisfy the (strong) persistence property. We also prove that dominating ideals of complete bipartite graphs are nearly normally torsion-free. In addition, we show that dominating ideals of h -wheel graphs, under certain condition, are normal. [ABSTRACT FROM AUTHOR]

An outer-independent triple Roman dominating function (OI[3]RDF) on a graph G = (V,E) is function f : V →{0, 1, 2, 3, 4} having the property that (i) if f(v) = 0, then v must have either a neighbor assigned 4 or two neighbors one of which is assigned 3 and the other at least 2 or v has three neighbors all assigned 2; (ii) no two vertices assigned 0 are adjacent; (iii) if f(v) = 1, then v must have either a neighbor assigned at least 3 or two neighbors assigned 2; (iv) if f(v) = 2, then v must have one neighbor assigned at least 2. The weight of an OI[3]RDF is the sum of its function value over the whole set of vertices, and the outer-independent triple Roman domination number of G is the minimum weight of an OI[3]RDF on G. In this paper, we continue the study of outer-independent triple Roman domination number of graphs by first presenting two sharp lower bounds for the outer-independent triple Roman domination number of trees. Then we strengthen the NP-complete result of the outer-independent triple Roman domination problem for bipartite graphs by showing that the problem remains NP-complete for a subclass of bipartite graphs, namely tree convex bipartite graphs, where two special trees are considered. [ABSTRACT FROM AUTHOR]

This paper studies the distributed bipartite state consensus tracking problem of discrete-time linear leader-following singular multi-agent systems (MASs). Compared with the traditional continuous-time linear dynamics, it is difficult to achieve the desired cooperative control of discrete-time counterpart since their stability regions are limited to the unit circle. In addition, in some practical scenarios, there are both cooperation and competition coexisting among followers. First, a new distributed state feedback control protocol is proposed based on the Gerschgorin circle theorem and the discrete algebraic Riccati equation. At the same time, by introducing the constant coupling gain associated with the system topology matrix, the global tracking error system can locate in the stable region of the unit circle. Under the structurally balanced condition of directed signed graph, it can be proved that all the agents of two opposite subgroups can achieve bipartite state tracking by Lyapunov stability theory and separation principle. Then, by using the cooperative–competitive interaction information of neighbours, a new distributed state observer is introduced to estimate the state of leader. Furthermore, when the states of followers are not known, an observer-based output feedback bipartite control protocol is proposed, which can also be applied to more general consensus control scenarios. Meanwhile, a bipartite state formation controller is given to achieve the formation control by making the followers to keep the desired relative positions with the leader. Finally, two simulation results are given to verify the feasibility and effectiveness of proposed algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we investigate bounds for the fault-tolerant metric dimension and adjacency fault-tolerant resolving set of corona product graphs. Let Q and R be two graphs with orders m1 and m2, respectively. The corona product of the graphs Q and R, denoted by Q ⊙R, is constructed by taking one copy of Q and m1 copies of R, connecting each vertex of the ith copy of R to the ith vertex of Q by an edge. For any integer k > 1, we recursively define the graph Q ⊙kR as Q ⊙kR = (Q ⊙k−1R) ⊙R. We present several results on the fault-tolerant metric dimension and the adjacency fault-tolerant resolving set of corona product graphs. Additionally, we explore the relationship between the fault-tolerant metric dimension and the adjacency fault-tolerant metric dimension of a graph Q. Finally, we determine the adjacency fault-tolerant metric dimension of path, cycle, complete, complete bipartite, and star graphs. [ABSTRACT FROM AUTHOR]

Let Γ(풲) be the Cayley graph of a finite Weyl groupoid 풲. In this paper, we show an existence of a Hamiltonian cycle of Γ(풲) for any 풲. We exactly draw a Hamiltonian cycle of Γ(풲) for any (resp. some) irreducible 풲 of rank three (resp. four). Moreover for the irreducible 풲 of rank three, we give a second largest eigenvalue of the adjacency matrix of Γ(풲), and know if Γ(풲) is a bipartite Ramanujan graph or not. [ABSTRACT FROM AUTHOR]

For a simple, undirected graph G (V , E) without isolated vertices, a function h : V → { ϕ , { 1 } , { 2 } , { 1 , 2 } } which satisfies the following two conditions is called a total 2-rainbow dominating function (T2RDF) of G. (i) For all u ∈ V , if h (u) = ϕ then ∪ v ∈ N (u) h (v) = { 1 , 2 } and (ii) Every u ∈ V with h (u) ≠ ϕ is adjacent to a vertex v with h (v) ≠ ϕ. The weight of a T2RDF h of G is the value h (V) = ∑ u ∈ V | h (u) |. The total 2-rainbow domination number is the minimum weight of a T2RDF on G and is denoted by γ t r 2 (G). The minimum total 2-rainbow domination problem (MT2RDP) is to find a T2RDF of minimum weight in the input graph. In this article, we show that the problem of deciding if G has a T2RDF of weight at most l for star convex bipartite graphs, comb convex bipartite graphs, split graphs and planar graphs is NP-complete. On the positive side, we show that MT2RDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, we show that MT2RDP cannot be approximated within (1 −) ln | V | for any > 0 unless P=NP and also propose 2 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for it. Further, we show that MT2RDP is APX-complete for graphs with maximum degree 4. Next, it is shown that domination problem and the total 2-rainbow domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MT2RDP is presented. [ABSTRACT FROM AUTHOR]

Rainbow antimagic coloring is the combination of antimagic labeling and rainbow coloring. The smallest number of colors induced from all edge weights of antimagic labeling is the rainbow antimagic connection number of G , denoted by rac (G). Given a graph G with vertex set V (G) and edge set E (G) , the function f from V (G) to { 1 , 2 , ... , | V (G) | } is a bijective function. The associated weight of an edge y z ∈ E (G) under f is w (y z) = f (y) + f (z). A path R in the vertex-labeled graph G is said to be a rainbow y − z path if for any two edges y z , y ′ z ′ ∈ E (R) it satisfies w (y z) ≠ w (y ′ z ′). The function f is called a rainbow antimagic labeling of G if there exists a rainbow y − z path for every two vertices y , z ∈ V (G). When we assign each edge y z with the color of the edge weight w (y z) , we say the graph G admits a rainbow antimagic coloring. In this paper, we show the new lower bound and exact value of the rainbow antimagic connection number of comb product of any tree and complete bipartite graph. [ABSTRACT FROM AUTHOR]

The concepts of domination and topological index hold great significance within the realm of graph theory. Therefore, it is pertinent to merge these concepts to derive the domination index of a graph. A novel concept of the domination index is introduced, which utilizes the domination degree of a vertex. The domination degree of a vertex a is defined as the minimum cardinality of a minimal dominating set (MDS) that includes a. Methods to find a MDS containing a particular vertex is also discussed in the study. The notion of domination degree and domination index are studied for graphs like complete graphs, complete bipartite, r − partite graphs, cycles, wheels, paths, book graphs, windmill graphs, Kragujevac trees. The study is extended to operation in graphs. Inequalities involving domination degree and already established graph parameters are discussed. An application of domination degree is discussed in facility allocation in a city. [ABSTRACT FROM AUTHOR]

In this paper, we introduce several new construction techniques of linear complimentary dual (LCD) codes. First, we show that if a LCD code is fixed by a transitive automorphism group, then the punctured code is also LCD. We show that several important families such as anti-primitive BCH codes and extended Gabidulin codes are LCD. Finally relationships among self-dual codes, λ-orthogonal matrices and LCD codes are studied. As an application we give LCD codes from Paley-type bipartite graph and from punctured MacDonalds codes. Further, we give a bound on some LCD codes. [ABSTRACT FROM AUTHOR]

Parallel paths of interconnection networks have attracted much attention in parallel computing systems, they are studied in terms of disjoint paths in an undirected graph G. A k -disjoint path cover (k-DPC for short) of a graph G is a set of k (internally) disjoint paths that altogether cover every vertice of the graph. A bipartite graph H is one-to-one bi-k-DPC if there is a k-DPC between any pair of vertices in different partite sets. A bipartite graph is hamiltonian laceable if there exists a hamiltonian path between any pair of vertices in different partite sets. The n -dimensional leaf-sort graph C F n has many good properties, including bipartite, symmetry, vertex-transitive. In this paper, we prove that C F n has one-to-one bi- (⌈ 3 n 2 ⌉ − 2) -DPC between any two vertices x and y in C F n , where x , y in different partite sets, and C F n is hamiltonian laceable. [ABSTRACT FROM AUTHOR]

For any bipartite graph G with bipartition V 1 and V 2 , a t -container C t (u , v) is a set of t internally disjoint paths P 1 , P 2 , ... , P t between two vertices u ∈ V 1 and v ∈ V 2 in G , i.e., C t (u , v) = { P 1 , P 2 , ... , P t }. Moreover, if V (P 1) ∪ V (P 2) ∪ ⋯ ∪ V (P t) = V (G) then C t (u , v) is called a spanning t -container, denoted by C t s l (u , v). The length of C t s l (u , v) = { P 1 , P 2 , ... , P t } is l (C t s l (u , v)) = max { l (P i) | 1 ≤ i ≤ t }. Besides, G is spanning t -laceable if there exists a spanning t -container between any two vertices u ∈ V 1 and v ∈ V 2 in G. Assume that u ∈ V 1 and v ∈ V 2 are two distinct vertices in a spanning t -laceable graph G. Let D t s l (u , v) be the collection of all C t s l (u , v) 's. Define the spanning t -wide distance between u and v in G , d t s l (u , v) = min { l (C t s l (u , v)) | C t s l (u , v) ∈ D t s l (u , v) } , and the spanning t -wide diameter of G , D t s l (G) = max { d t s l (u , v) | u ∈ V 1 , v ∈ V 2 }. In particular, the spanning wide diameter of G is D κ s l (G) , where κ is the connectivity of G. In the paper we first provide the lower and upper bounds of the wide diameter of a bipartite graph, and then determine the exact values of the spanning wide diameters of the spider web networks S W (m , n) for n = 2 , 4. [ABSTRACT FROM AUTHOR]

A set D ⊆ V of a graph G = (V , E) is called a connected power dominating set of G if G [ D ] , the subgraph induced by D , is connected and every vertex in the graph can be observed from D , following the two observation rules for power system monitoring: Rule 1 : if v ∈ D , then v can observe itself and all its neighbors, and Rule 2 : for an already observed vertex whose all neighbors except one are observed, then the only unobserved neighbor becomes observed as well. Given a graph G , Minimum Connected Power Domination is to find a connected power dominating set of minimum cardinality of G and Decide Connected Power Domination is the decision version of Minimum Connected Power Domination. Decide Connected Power Domination is known to be N P -complete for general graphs. In this paper, we prove that Decide Connected Power Domination remains N P -complete for star-convex bipartite graphs, perfect elimination bipartite graphs and split graphs. This answers some open problems posed in [B. Brimkov, D. Mikesell and L. Smith, Connected power domination in graphs, J. Comb. Optim. 38(1) (2019) 292–315]. On the positive side, we show that Minimum Connected Power Domination is polynomial-time solvable for chain graphs, a proper subclass of perfect elimination bipartite graph, and for threshold graphs, a proper subclass of split graphs. Further, we show that Minimum Connected Power Domination cannot be approximated within (1 −) ln | V | for any > 0 unless P = N P , for bipartite graphs as well as for chordal graphs. Finally, we show that Minimum Connected Power Domination is APX -hard for bounded degree graphs. [ABSTRACT FROM AUTHOR]

The conditional fractional matching preclusion number (CFMP number for short) fmp1(G) of a graph G is the minimum number of edges whose deletion results in a graph without isolated vertices and without fractional perfect matchings. In this paper, we study the CFMP number of complete graphs, complete bipartite graphs and twisted cubes. Also, we give Nordhaus–Gaddum-type results for the CFMP numbers of general graphs. [ABSTRACT FROM AUTHOR]

The mobility pattern of a population plays a key role in the spread of epidemics. Despite extensive work on epidemic spreading, little attention has been paid to the impact of subpopulation size. This paper investigates the spread of epidemics on a bipartite metapopulation network considering recurrent mobility patterns and different sizes of subpopulations. With the Markovian process approach, the epidemic threshold can be predicted as a function of subpopulation size and epidemic parameters. Simulation and theoretical results indicate that there exists a critical mobility intensity below which the epidemic will be eliminated, while limiting the size of the subpopulation can suppress the epidemic. Additionally, the epidemic threshold will approach zero when the size of the public area is large. The results can help the prevention of epidemic spreading under recurrent crowd mobility. [ABSTRACT FROM AUTHOR]

For k,n ≥ 2, a (k,n)-firecracker graph, denoted by Fk,n, is obtained by concatenation of k n-star graphs by connecting one leaf from each n-star graph. Given a finite simple graph G, one can associate a simplicial complex Δ(G). In this paper, we compute all the graded Betti numbers of the edge ideal I(F2,n) of the firecracker graph F2,n by using the combinatorial data associated with the simplicial complex Δ(F2,n). We also find the regularity of the ideals I(Fk,n). Further, using the domination parameters of the graphs, we explicitly compute the projective dimension of I(Fk,n). [ABSTRACT FROM AUTHOR]

Multi-interest sequential recommendations leverage users' historical behavior to provide recommendations that match multiple interests. Most of these methods have not fully extracted higher-order information hidden in users' interactions and have overlooked the multiple features of items. To this end, this paper proposes a multi-interest model called "multi-interest sequential recommendation with simplified graph convolution and item multi-features (SGCMF)". Firstly, a simplified graph convolution module is designed based on bipartite graphs, which utilizes mean pooling to aggregate neighboring information and employs a feedforward neural network (FNN) for nonlinear transformations and combinations. This method reduces redundant information and captures higher-order relationships, thereby simplifying the complexity of modeling high-order interactions and improving prediction accuracy. Secondly, an item multi-feature extraction module is proposed, which represents item features with multiple vectors, and analyzes each feature from multiple perspectives while preserving important relationships between features. The model correlates multiple features of the item with user interests, thereby achieving a fine-grained analysis of user interests. Extensive experiments are conducted on five real-world scenarios, and the results are compared with state-of-the-art methods. The experimental results show that SGCMF outperforms other baselines. [ABSTRACT FROM AUTHOR]

This paper investigates a leader–follower consensus problem of multi-layer networks and understands the role of leader's allocations in the process of consensus. Leader–follower coherence quantified by the spectrum measures the extent of consensus between leaders and followers in the system under additive noise. In order to study the exact interplay between leader–follower coherence and leader's allocations, we choose complete multi-partite networks as network models and assign the leaders into different layers. Based on the network construction, we obtain exact solutions of leader–follower coherence with freely assigned leaders and reveal that the allocations of leaders have a significant impact on the coherence. Finally, we compare the leader–follower coherence and leaderless coherence of bipartite networks when the number of leaders and network size satisfies certain conditions. [ABSTRACT FROM AUTHOR]

A simple undirected regular graph is said to be semisymmetric if it is edge-transitive but not vertex-transitive. For a semisymmetric graph Γ of order 2 p 3 , p a prime, it is well known that Γ is bipartite with two biparts having equal size. The complete classification of such graphs has been given for the full automorphism group Aut (Γ) acting unfaithfully on at least one bipart of Γ , which shows that there is only one infinite family of such graphs with valency p 2. The graphs of this kind have been determined when Aut (Γ) acts faithfully and primitively on at least one bipart of Γ , and thus there is only one remaining case for classifying such graphs of valency p 2 , Aut (Γ) acting faithfully and imprimitively on both biparts of Γ , which is dealt with in this paper. As a result, there is only one infinite family of semisymmetric graphs of order 2 p 3 with valency p 2. [ABSTRACT FROM AUTHOR]

This paper is concerned with designing algorithms for and analyzing the computational complexity of the partial vertex cover problem in trees. Graphs (and trees) are frequently used to model risk management in various systems. In particular, Caskurlu et al. in [4] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. In this paper, we focus on a special case of the partial vertex cover problem, when the input graph is a tree. We consider four possible versions of this setting, depending on whether or not, the vertices and edges are weighted. Two of these versions, where edges are assumed to be unweighted, are known to be polynomial-time solvable. However, the computational complexity of this problem with weighted edges, and possibly with weighted vertices, remained open. The main contribution of this paper is to resolve these questions by fully characterizing which variants of partial vertex cover remain NP-hard in trees, and which can be solved in polynomial time. In the paper, we propose two pseudo-polynomial DP-based algorithms for the most general case in which weights are present on both the edges and the vertices of the tree. One of these algorithms leads to a polynomial-time procedure, when weights are confined to the edges of the tree. The insights used in this algorithm are combined with additional scaling ideas to derive an FPTAS for the general case. A secondary contribution of this work is to propose a novel way of using centroid decompositions in trees, which could be useful in other settings as well. [ABSTRACT FROM AUTHOR]

An Italian dominating function of a graph G = (V , E) with vertex set V is defined as a function f : V → { 0 , 1 , 2 } , which satisfies the condition that for every v ∈ V with f (v) = 0 , ∑ u ∈ N (v) f (u) ≥ 2. The weight of an Italian dominating function on G is the sum f (V) = ∑ u ∈ V f (v) and the Italian dominating number, and γ I (G) indicates the minimum weight of an Italian dominating function f. In this paper, the structure of the generalized Sierpiński networks is investigated using the bounds of Italian domination number of graphs and the methods of mathematical induction and reduction to absurdity. Then, the Italian domination on the generalized Sierpiński networks S (G , t) is obtained, where G denotes any special class of Path P n , Cycle C n , Wheel W n , Star K 1 , n , and complete bipartite graph K m , n . [ABSTRACT FROM AUTHOR]

The distance energy of a connected graph G is the sum of absolute values of the eigenvalues of the distance matrix of G. In this paper, we study how the distance energy of the complete split graph G S (m , n) = K m + K ¯ n changes when an edge is deleted from it. The complete split graph G S (m , n) consists of a clique on m vertices and an independent set on n vertices in which each vertex of the clique is adjacent to each vertex of the independent set. We prove that the distance energy of the complete split graph G S (m , n) always increases when an edge is deleted from it. [ABSTRACT FROM AUTHOR]

Graph protection using mobile guards has received a lot of attention in the literature. It has been considered in different forms, including Eternal Dominating set, Eternal Independent set and Eternal Vertex Cover set. In this paper, we introduce and study two new models of graph protection, namely Eternal Feedback Vertex Sets (EFVS) and m-Eternal Feedback Vertex Sets (m-EFVS). Both models are based on an initial selection of a feedback vertex set (FVS), where a vertex in FVS can be replaced with a neighboring vertex such that the resulting set is a FVS too. We prove bounds for both the eternal and m-eternal feedback vertex numbers on, mainly, distance graphs, circulant graphs and grids. Also, we deduce other inequalities for both parameters on cycles, complete graphs and complete bipartite graphs. [ABSTRACT FROM AUTHOR]

In this paper, we quantitatively study the dynamics of the tripartite entanglement of the three-mode Gaussian state in a cavity-free optomechanical system. After deriving the explicit form of the evolved state matrix covariance, we elucidate in detail the evidence of entanglement monogamy in different mode partitions, based on Coofman–Kundu–Wotters inequalities, using the Gaussian Contangle quantifying bipartite entanglement. Next, we focus on the genuine tripartite entanglement quantified by means of the Residual Gaussian Contangle. [ABSTRACT FROM AUTHOR]

Broadcasting is a fundamental problem in the information dissemination area. In classical broadcasting, a message must be sent from one network member to all other members as rapidly as feasible. Although it has been demonstrated that this problem is NP-Hard for arbitrary graphs, it has several applications in various fields. As a result, the universal lists model, replicating real-world restrictions like the memory limits of nodes in large networks, is introduced as a branch of this problem in the literature. In the universal lists model, each node is equipped with a fixed list and has to follow the list regardless of the originator. In this study, we focus on the non-adaptive branch of universal lists broadcasting. In this regard, we establish the optimal broadcast time of k -ary trees and binomial trees under the non-adaptive model and provide an upper bound for complete bipartite graphs. We also improved a general upper bound for trees under the same model and showed that our upper bound cannot be improved in general. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the concepts of (perfect) Roman and Italian dominations to (perfect) strong Roman and Roman k -domination for arbitrary positive integer k. These generalizations cover some of previous ones. After some comparison of their domination numbers, as a first study of these concepts, we study the (perfect, strong, perfect strong) Roman k -domination numbers of complete bipartite graphs. [ABSTRACT FROM AUTHOR]

The crossing number of a graph G , denoted by cr (G) , is defined to be the minimum number of crossings that arise among all its drawings in the plane. This concept has been of interest to many researchers who have studied it for many families of graphs. In this paper, we introduce the crossing number of Cartesian product of sunlet graph S m with path P n . Further, we prove that the crossing number of S m □ P 2 is equal to m , along with giving a conjecture for the general case. In addition, we utilize the vertex's rotation concept in order to prove some necessary conditions for the complete bipartite graph K m , n to be optimal when it is drawn in the plane, by presenting an upper bound for the crossing number of any subgraph in it together with determining the exact number of crossings in case the vertices of subgraph have the same rotation. [ABSTRACT FROM AUTHOR]

To provide solutions to the world's global challenges, there is an urgent demand for wise organisations, wise leadership, wise workers, and most importantly, for wise actions. Since the mid-1990s, Knowledge Management (KM) as a discipline and practice has emerged internationally, and it has passed through several phases of development. Simultaneously, in the last four decades we have experienced a growth of wisdom research and intensified discourses about Wisdom Management (WM) as a possible venue for dealing with wicked problems. The dilemma is whether the current sixth phase of KM is able to address the global problems of the world. Therefore, this conceptual paper seeks to answer the question if WM will complement or replace KM. This paper explores the evolutionary phases of KM; it presents the discourses about WM, and it discovers the presence of wisdom in the KM literature (1995–2022). The research approach is explorative and inductive. Methods of Computational Social Sciences and RStudio as an Integrated Development Environment (IDE) are utilised for analysing, visualising, and interpreting the data. This paper analyses 255 wisdom-related keywords that emerged from 39 sources written by 50 authors. The three data analyses methods are: word cloud data analysis; dictionary-based data analysis, and bipartite network analysis. The findings are presented in word clouds; keywords frequency; bipartite network, and in a synthesised framework to show the similar and different concepts of KM and WM. The novelty value of this paper is the result of the bipartite network analysis that allows to identify how authors and wisdom-related keywords are connected with the same word nodes. This paper contributes to KM because it is the first study to explore and illustrate the presence of wisdom attributes in the KM literature. [ABSTRACT FROM AUTHOR]

Let G be a graph. A vertex-cut S of G is said to be k-restricted if every component of G − S has at least k vertices, and cyclic if G − S has at least two components which contain a cycle. The minimum cardinality over all k -restricted vertex-cuts of G is called the k-restricted connectivity of G and is denoted by κ k (G). Also the minimum cardinality over all cyclic vertex-cuts of G is called the cyclic connectivity of graph G and is denoted by κ c (G). In this paper, the k -restricted connectivity and cyclic connectivity of the direct product of two graphs G 1 and G 2 is obtained for some k ≥ 2 , where G 1 is a complete graph, and G 2 is a complete graph, a complete bipartite graph or a cycle. [ABSTRACT FROM AUTHOR]

The Bell inequalities stand at the cornerstone of the developments of quantum theory on both the foundational and applied side. The discussion started as a way to test whether the quantum description of reality is complete or not, but it developed in such a way that a new research area stemmed from it, namely quantum information. Far from being and exhausted topic, in this paper, we present a constructive and geometrically intuitive description of the local polytope and its facets in a bipartite Bell scenario with two dichotomic measurements per party. [ABSTRACT FROM AUTHOR]

The partially balanced incomplete block (PBIB)-designs and association schemes arising from different graph parameters is a well-studied concept. In this paper, we define and construct PBIB-designs with association schemes in strongly regular graphs through the nodes belonging to the diametral paths as blocks. A (v , b , r , k , λ , μ) -design, called a diametral-design (in short) over a strongly regular graph G = (V , E) of degree d , diameter diam (G) , is an ordered pair D = (V , B) , where V = V (G) and B is the set of all diametral paths of G , called blocks, containing the nodes belonging to the diametral paths, satisfying the following conditions: (i) If x , y ∈ V and { x , y } ∈ E , then there are exactly λ blocks containing { x , y } ; (ii) If x , y ∈ V , x ≠ y and { x , y } ∉ E , then there are exactly μ -blocks containing { x , y }. We construct PBIB-designs with two-association schemes through diametral paths corresponding to the strongly regular graphs such as the square lattice graphs L 2 (n) , the triangular graphs T (n) , the three Chang graphs, the Petersen graph, the Shrikhande graph, the Clebsch graph, the complement of Clebsch graph, the complement of Schläfli graph, complete bipartite graphs, the Hoffman–Singleton graph, etc. and in each case we give the composition of the diametral paths. These serve as extensions for the collection of near impossible class of strongly regular graphs with given parameters having two-association schemes. [ABSTRACT FROM AUTHOR]

Let G be a finite group and A G be the automorphism group of G (i.e. Aut (G)). We associated a bipartite graph, denoted by Γ G , to G and its automorphism group Aut (G) as follows: two parts of the vertex set are G \ L (G , Z (G)) and A G \ Aut c (G) , where L (G , Z (G)) is the set of elements g ∈ G such that g − 1 α (g) ∈ Z (G) for all α ∈ A G and Aut c (G) is the set of automorphisms β ∈ A G such that g − 1 β (g) ∈ Z (G) for all g ∈ G. Two vertices g ∈ G \ L (G , Z (G)) and α ∈ A G \ Aut c (G) are adjacent if and only if g − 1 α (g) ∉ Z (G). In this paper, we investigate some fundamental properties of Γ G such as connectivity, diameter, girth, Hamiltonian, independence and dominating numbers. Moreover, planarity and outer planarity of the graph are studied. [ABSTRACT FROM AUTHOR]

Two recent publications describe realizable Gauss diagrams using conditions stating that the number of chords in certain sets of chords is even or odd. We demonstrate that these descriptions are incorrect by finding multiple counter-examples. However, the idea of having a parity-based description of realizable Gauss diagrams is attractive. We recall that realizability of Gauss diagrams as touch curves can be described via bipartite graphs. We show that realizable Gauss diagrams can be described via bipartite graphs. [ABSTRACT FROM AUTHOR]

We study the Maximum Bipartite Subgraph (M B S) problem, which is defined as follows. Given a set S of n geometric objects in the plane, we want to compute a maximum-size subset S ′ ⊆ S such that the intersection graph of the objects in S ′ is bipartite. We first give an O (n 2) -time algorithm that computes an almost optimal solution for the problem on circular-arc graphs. We show that the M B S problem is N P -hard on geometric graphs for which the maximum independent set is N P -hard (hence, it is N P -hard even on unit squares and unit disks). On the other hand, we give a P T A S for the problem on unit squares and unit disks. Moreover, we show fast approximation algorithms with small-constant factors for the problem on unit squares, unit disks, and unit-height axis parallel rectangles. Additionally, we prove that the Maximum Triangle-free Subgraph (M T F S) problem is NP-hard for axis-parallel rectangles. Here the objective is the same as that of the M B S except the intersection graph induced by the set S ′ needs to be triangle-free only (instead of being bipartite). [ABSTRACT FROM AUTHOR]

We characterize the completely determined Borel subsets of HYP as exactly the Δ 1 (L ω 1 c k ) subsets of HYP. As a result, HYP believes there is a Borel well-ordering of the reals, that the Borel Dual Ramsey Theorem fails, and that every Borel d-regular bipartite graph has a Borel perfect matching, among other examples. Therefore, the Borel Dual Ramsey Theorem and several theorems of descriptive combinatorics are not theories of hyperarithmetic analysis. In the case of the Borel Dual Ramsey Theorem, this answers a question of Astor, Dzhafarov, Montalbán, Solomon and the third author. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the intersection graphs of subtrees in a cactus, called cactus subtree graphs. A max-k-cliquesubgraph of a graph is an induced subgraph whose maximum clique has at most k vertices. We describe a polynomial time algorithm to find a maximum weight max- k -clique subgraph in a cactus subtree graph when k is fixed. In perfect graphs this problem is equivalent to the maximum weight k -colorable subgraph problem. In many applications like scheduling production lines and communication networks on imperfect graphs, a maximum max- k -clique subgraph solution is better than a maximum k -colorable subgraph solution. In addition, we describe cactus subtree graphs polynomial time algorithms for recognition, maximum independent sets, maximum cliques, maximum induced bipartite graphs, maximum induced forests and minimum feedback vertex sets. [ABSTRACT FROM AUTHOR]

Spanness of fuzzy graph is introduced. By spanness, a new vulnerability parameter, span integrity is defined in fuzzy graph. The span integrity values are found for path, cycle, complete fuzzy graph, complete bipartite fuzzy graphs. Path and cycle with node strength sequence are discussed. Brain network is modeled as a fuzzy graph and Span integrity is applied to the brain network. Span integrity of fuzzy brain network is calculated for before and after meditation models. The results are compared and the improvement in the stability of the brain network is shown. [ABSTRACT FROM AUTHOR]

In this paper, we introduced the new concept detour global domination number for splitting graph of standard graph. The detour global dominating sets in some standard and special graphs are determined. First we recollect the concept of splitting graph of a graph and we produce some results based on the detour global domination number of splitting graph of star graph, bistar graph and complete bipartite graph. A set S is called a detour global dominating set of G if S is both detour and global dominating set of G. The detour global domination number is the minimum cardinality of a detour global dominating set in G. [ABSTRACT FROM AUTHOR]

Let I be an ideal of the form I = ⋂ 1 ≤ i < j ≤ n P i , j w i , j in a polynomial ring R = K [ x 1 , x 2 , ... , x n ] over a field K , where P i , j is a prime ideal generated by variables { x 1 , x 2 , ... , x n } ∖ { x i , x j } for 1 ≤ i < j ≤ n. In this paper, we will characterize the level property of R / I in the case w i , j takes a positive value α or β. In such a case, we also give an explicit formula for the last Betti number of this ring. [ABSTRACT FROM AUTHOR]

Given two disjoint vertex-sets, S = { s 1 , ... , s k } and T = { t 1 , ... , t k } in a graph, a paired many-to-many  k -disjoint path cover joining S and T is a set of pairwise vertex-disjoint paths { P 1 , ... , P k } that altogether cover every vertex of the graph, in which each path P i runs from s i to t i . In this paper, we reveal that a bipartite torus-like graph, if built from lower dimensional torus-like graphs that have good disjoint-path-cover properties, retain such good property. As a result, an m -dimensional bipartite torus, m ≥ 3 , with at most 2 m − 4 edge faults has a paired many-to-many 3 -disjoint path cover joining arbitrary disjoint sets S and T of size 3 each such that S ∪ T contains the equal numbers of vertices from different parts of the bipartition. [ABSTRACT FROM AUTHOR]

The bipartization problem for a graph G asks for finding a subset S of V (G) such that the induced subgraph G [ S ] is bipartite and | S | is maximized. This problem has significant applications in the via minimization of VLSI design. The problem has been proved NP-complete and the fixed parameter solvability has been known in the literature. This paper presents several polynomial-time algorithms for special graph families, such as split graphs, co-bipartite graphs, chordal graphs, and permutation graphs. [ABSTRACT FROM AUTHOR]