Let G be a simple and connected graph. When G graph is added by new vertex v' in graph G (where the number of vertex v' corresponds to vertex v) such that if v1 adjacent to v2 in G then v1 will ...adjacent to v2 in G. The G graph is called split graph. When G has m v'-vertices, then it is called m-splitting graph. Let V(G) is a set of vertices and let E(G) is a set of edges. They are two sets which form graph G. W is called a local adjacency resolving set of G if for every two distinct vertices x,y and x adjacent with y then rA(x|W) = rA(y|W). The local adjacency metric basis is a minimum local adjacency resolving set in G. The cardinality of vertices in the basis is a local adjacency metric dimension of G (dimA,l(G)). We present the exact value of local adjacency metric dimension of m-splitting related wheel graphs.
If G, H and F are finite and simple graphs, notation F → (G, H) means that for any red-blue coloring of the edges of F, there is either a red subgraph isomorphic to G or a blue subgraph isomorphic to ...H. A graph F is a Ramsey (G, H)-minimal graph if F → (G, H) and for every e ∈ E(F), graph F − e ↛ (G, H). The class of all Ramsey (G, H)-minimal graphs (up to isomorphism) will be denoted by R(G, H). The characterization of all graphs in the infinite class R(P3, Pn) is still open, for any n ≥ 4. In this paper, we find an infinite families of trees in R(P3, P5). We determine how to construct unicyclic graphs in R(P3, Pn), for any n ≥ 5 from trees in the same class. Further, we give some properties for the unicyclic graphs constructed from trees in R(P3, Pn), for any n ≥ 5.
Given two graphs H1 and H2, a graph is (H1,H2)-free if it contains no induced subgraph isomorphic to H1 or H2. Let Pt and Ct be the path and the cycle on t vertices, respectively. A banner is the ...graph obtained from a C4 by adding a new vertex and making it adjacent to exactly one vertex of the C4. In this paper, we show that there are finitely many k-critical (P6,banner)-free graphs for k=4 and k=5. For k=4, we characterize all such graphs. Our results generalize previous results on k-critical (P6,C4)-free graphs for k=4 and k=5.
In this paper, we have obtained the total chromatic number for some classes of Cayley graphs, particularly the Unitary Cayley graphs on even order and some other Circulant graphs. We have also proved ...the Total Coloring Conjecture for some perfect Cayley graphs.
•147 publications related to knowledge graph reasoning are reviewed.•The review outlines different knowledge graph reasoning methods.•The remaining challenges of knowledge graph reasoning and its ...applications are discussed.•The review reveals opportunities for future knowledge graph reasoning research.
Mining valuable hidden knowledge from large-scale data relies on the support of reasoning technology. Knowledge graphs, as a new type of knowledge representation, have gained much attention in natural language processing. Knowledge graphs can effectively organize and represent knowledge so that it can be efficiently utilized in advanced applications. Recently, reasoning over knowledge graphs has become a hot research topic, since it can obtain new knowledge and conclusions from existing data. Herein we review the basic concept and definitions of knowledge reasoning and the methods for reasoning over knowledge graphs. Specifically, we dissect the reasoning methods into three categories: rule-based reasoning, distributed representation-based reasoning and neural network-based reasoning. We also review the related applications of knowledge graph reasoning, such as knowledge graph completion, question answering, and recommender systems. Finally, we discuss the remaining challenges and research opportunities for knowledge graph reasoning.
A graph G is a probe unit interval graph if its vertex set can be partitioned into a set P of probe vertices and a stable set N of nonprobe vertices, so that a unit interval graph can be obtained by ...adding a set of edges whose endpoints belong to N. A partitioned graph is a graph having a prescribed partition into P and N. In this article we present structural characterizations for those partitioned interval graphs and unpartitioned interval graphs which are probe unit interval graphs, in terms of certain characteristics of their interval models. These characterizations lead to characterizations of probe unit interval graphs within the class of interval graphs by minimal forbidden induced subgraphs.
On Total Coloring of Some Classes of Regular Graphs Prajnanaswaroopa, Shantharam; Geetha, Jayabalan; Somasundaram, Kanagasabapathi ...
Taiwanese journal of mathematics,
08/2022, Volume:
26, Issue:
4
Journal Article
Peer reviewed
Open access
In this paper, we have obtained upper bounds for the total chromatic number of some classes of Cayley graphs, odd graphs and mock threshold graphs.
Learning Graph Matching Caetano, T.S.; McAuley, J.J.; Li Cheng ...
IEEE transactions on pattern analysis and machine intelligence,
06/2009, Volume:
31, Issue:
6
Journal Article
Peer reviewed
Open access
As a fundamental problem in pattern recognition, graph matching has applications in a variety of fields, from computer vision to computational biology. In graph matching, patterns are modeled as ...graphs and pattern recognition amounts to finding a correspondence between the nodes of different graphs. Many formulations of this problem can be cast in general as a quadratic assignment problem, where a linear term in the objective function encodes node compatibility and a quadratic term encodes edge compatibility. The main research focus in this theme is about designing efficient algorithms for approximately solving the quadratic assignment problem, since it is NP-hard. In this paper we turn our attention to a different question: how to estimate compatibility functions such that the solution of the resulting graph matching problem best matches the expected solution that a human would manually provide. We present a method for learning graph matching: the training examples are pairs of graphs and the 'labels' are matches between them. Our experimental results reveal that learning can substantially improve the performance of standard graph matching algorithms. In particular, we find that simple linear assignment with such a learning scheme outperforms Graduated Assignment with bistochastic normalisation, a state-of-the-art quadratic assignment relaxation algorithm.
We show that counting Hamiltonian cycles on quartic 4-vertex-connected planar graphs is
#
P
-complete under many-one counting (“weakly parsimonious”) reductions, and that no Fully Polynomial-time ...Randomized Approximation Scheme (FPRAS) can exist for this integer counting problem unless
N
P
=
R
P
.
Estimating the probability that the Erdős-Rényi random graph Gn,m is H-free, for a fixed graph H, is one of the fundamental problems in random graph theory. If H is non-bipartite and m is such that ...each edge of Gn,m belongs to a copy of H′ for every H′⊆H, in expectation, then it is known that Gn,m is H-free with probability exp(−Θ(m)). The KŁR conjecture, slightly rephrased, states that if we further condition on uniform edge distribution, the archetypal property of random graphs, the probability of being H-free becomes superexponentially small in the number of edges. While being interesting on its own, the conjecture has received significant attention due to its connection with the sparse regularity lemma, and the many results in random graphs that follow. It was proven by Balogh, Morris, and Samotij and, independently, by Saxton and Thomason, as one of the first applications of the hypergraph containers method. We give a new direct proof using induction.
PDF
