摘要 :
In this paper, we study the complexity of recognizing powers of chordal graphs and its subclasses. We present the first polynomial time algorithm to recognize squares of proper interval graphs and give an outline of an algorithm t...
展开
In this paper, we study the complexity of recognizing powers of chordal graphs and its subclasses. We present the first polynomial time algorithm to recognize squares of proper interval graphs and give an outline of an algorithm to recognize kth powers of proper interval graphs for every natural number k. These are the first results of this type for a family of graphs that contains arbitrarily large cliques. On the other hand, we show the NP-completeness of recognizing squares of chordal graphs, recognizing squares of split graphs, and recognizing chordal graphs that are squares of some graph.
收起
摘要 :
The energy of a graph is the sum of the moduli of the eigenvalues of its adjacency matrix. We study the energy of integral circulant graphs, also called gcd graphs, which can be characterized by their vertex count n and a set D of...
展开
The energy of a graph is the sum of the moduli of the eigenvalues of its adjacency matrix. We study the energy of integral circulant graphs, also called gcd graphs, which can be characterized by their vertex count n and a set D of divisors of n in such a way that they have vertex set ~(Zn) and edge set a,b:a,b∈ ~(Zn),gcd(a-b,n)∈D. For a fixed prime power n= ~(ps) and a fixed divisor set size |D|=r, we analyse the maximal energy among all matching integral circulant graphs. Let p ~(a1)
摘要 :
In this paper, we investigate when the unit, unitary and total graphs have planar line graph, and also we study the case when these line graphs are ring graph or outerplanar.
摘要 :
Abstract Graph mining is a process of obtaining one or more sub-graphs and has been a very attractive research topic over the last two decades. It has found many practical applications dealing with real world problems in variety o...
展开
Abstract Graph mining is a process of obtaining one or more sub-graphs and has been a very attractive research topic over the last two decades. It has found many practical applications dealing with real world problems in variety of domains like Social Network Analysis, Designing of Computer Networks, Study of Chemical Reactions, Bio Informatics, Program Flow Structures, Image Processing, Enterprise data, Sparse Matrix ordering and many more. For these applications, many graph classification and Graph Clustering algorithms are evolved. This paper presents a comprehensive survey of published work in Graph Mining by grouping them in a broad taxonomy. For each of these groups in the taxonomy, the basic concepts of the algorithms are covered in detail by mentioning the contributions of various authors to the basic concepts of each group. Furthermore, common issues in graph mining algorithms, such as clustering, partitioning, visualization of graphs, are also elaborated. Standard datasets available for graph mining are stated as well.
收起
摘要 :
Let B be a commutative ring with nonzero identity and J(R) be the Jacobson radical of R. The Jacobson graph of B, denoted by JR, is a graph with vertex-set B \ J(R), such that two distinct vertices a and b in B \ J(R) are adjacent...
展开
Let B be a commutative ring with nonzero identity and J(R) be the Jacobson radical of R. The Jacobson graph of B, denoted by JR, is a graph with vertex-set B \ J(R), such that two distinct vertices a and b in B \ J(R) are adjacent if and only if 1 - ab is not a unit of B. Also, the line graph of the Jacobson graph is denoted by L(Jr). In this paper, we characterize all finite commutative rings R such that the graphs L(JR) are planar, toroidal or projective.
收起
摘要 :
Certain graph-theoretic properties and alternative definitions of the Gray graph, the smallest known cubic edge- but not vertex-transitive graph, are discussed in detail. (C) 2000 John Wiley & Sons, Inc. [References: 5]
摘要 :
In this paper, we solve graph equations L(G) = m (H), M(G) = m (H), L (G) = n (H), M (G) = n(H), J (G) = m(H), M(G) = m(H), J(G) = n(H) and M(G) = n(H). The equality symbol '=' stands for an isomorphism between two graphs.
摘要 :
An upward plane drawing of a directed acyclic graph is a plane drawing of the digraph in which each directed edge is represented as a curve monotone increasing in the vertical direction. Thomassen has given a nonalgorithmic, graph...
展开
An upward plane drawing of a directed acyclic graph is a plane drawing of the digraph in which each directed edge is represented as a curve monotone increasing in the vertical direction. Thomassen has given a nonalgorithmic, graph-theoretic characterization of those directed graphs with a single source that admit an upward plane drawing. This paper presents an efficient algorithm to test whether a given single-source acyclic digraph has an upward plane drawing and, if so, to find a representation of one such drawing. This result is made more significant in light of the recent proof by Garg and Tamassia that the problem is NP-complete for general digraphs. The algorithm decomposes the digraph into biconnected and triconnected components and defines conditions for merging the components into an upward plane drawing of the original digraph. To handle the triconnected components, we provide a linear algorithm to test whether a given plane drawing of a single-source digraph admits an upward plane drawing with the same faces and outer face, which also gives a simpler, algorithmic proof of Thomassen's result. The entire testing algorithm (for general single-source directed acyclic graphs) operates in O(n(2)) time and O(n) space (n being the number of vertices in the input digraph) and represents the first polynomial-time solution to the problem. [References: 27]
收起
摘要 :
? 2023 Elsevier B.V.This comprehensive review provides an in-depth analysis of graph theory, various graph types, and the role of graph visualization in scientific studies. Graphs serve as powerful tools for modeling and analyzing...
展开
? 2023 Elsevier B.V.This comprehensive review provides an in-depth analysis of graph theory, various graph types, and the role of graph visualization in scientific studies. Graphs serve as powerful tools for modeling and analyzing complex systems in diverse disciplines. The introduction highlights the importance of graphs as a visual representation in scientific research, enabling a better understanding of complex data. Infographics and knowledge graphs have gained significant popularity in recent years due to their effectiveness in conveying information. The review starts by exploring the foundations of graph theory, covering key concepts, algorithms, and applications. It discusses the different types of graphs, including directed, undirected, weighted, and bipartite graphs, and their specific use cases in scientific studies. Special attention is given to special graphs, such as complete graphs, trees, and social networks, which have unique properties and play a significant role in various scientific domains. The review showcases their applications and contributions in fields like biology, social sciences, network analysis, and data mining. Graph visualization emerges as a crucial aspect of understanding and interpreting complex data structures. The review emphasizes the challenges and advancements in graph visualization techniques, enabling researchers to effectively communicate and analyze graph-based information. In conclusion, this comprehensive review serves as a valuable resource for researchers in understanding the principles and applications of graph theory in scientific studies. The exploration of graph types, special graphs, and graph visualization techniques provides insights into the diverse uses and potential of graphs in various scientific disciplines.
收起
摘要 :
In this paper, we establish the possibility of embedding a graph as an induced subgraph in an elegant graph, a harmonious graph, a felicitous graph, cordial graph, odd-graceful graph, polychrome graph and on strongly c-harmonious ...
展开
In this paper, we establish the possibility of embedding a graph as an induced subgraph in an elegant graph, a harmonious graph, a felicitous graph, cordial graph, odd-graceful graph, polychrome graph and on strongly c-harmonious graph, each with a given property, leading to prove the NP-completeness of some parameters like chromatic number, clique number, domination number and independence number of these graphs.
收起
原文获取