We classify tetravalent G-half-arc-transitive graphs Γ of order p2q2, where G ⩽ Aut Γ and p, q are distinct odd primes. This result involves a subclass of tetravalent half-arc-transitive graphs of ...cube-free order.
Many T copies in H-free graphs Alon, Noga; Shikhelman, Clara
Journal of combinatorial theory. Series B,
November 2016, 2016-11-00, Volume:
121
Journal Article
Peer reviewed
Open access
For two graphs T and H with no isolated vertices and for an integer n, let ex(n,T,H) denote the maximum possible number of copies of T in an H-free graph on n vertices. The study of this function ...when T=K2 is a single edge is the main subject of extremal graph theory. In the present paper we investigate the general function, focusing on the cases of triangles, complete graphs, complete bipartite graphs and trees. These cases reveal several interesting phenomena. Three representative results are:(i)ex(n,K3,C5)≤(1+o(1))32n3/2,(ii)For any fixed m, s≥2m−2 and t≥(s−1)!+1, ex(n,Km,Ks,t)=Θ(nm−(m2)/s), and(iii)For any two trees H and T, ex(n,T,H)=Θ(nm) where m=m(T,H) is an integer depending on H and T (its precise definition is given in Section 1).
The first result improves (slightly) an estimate of Bollobás and Győri. The proofs combine combinatorial and probabilistic arguments with simple spectral techniques.
Graph theory provides a language for studying the structure of relations, and it is often used to study interactions over time too. However, it poorly captures the intrinsically temporal and ...structural nature of interactions, which calls for a dedicated formalism. In this paper, we generalize graph concepts to cope with both aspects in a consistent way. We start with elementary concepts like density, clusters, or paths, and derive from them more advanced concepts like cliques, degrees, clustering coefficients, or connected components. We obtain a language to directly deal with interactions over time, similar to the language provided by graphs to deal with relations. This formalism is self-consistent: usual relations between different concepts are preserved. It is also consistent with graph theory: graph concepts are special cases of the ones we introduce. This makes it easy to generalize higher level objects such as quotient graphs, line graphs,
k
-cores, and centralities. This paper also considers discrete versus continuous time assumptions, instantaneous links, and extensions to more complex cases.
We survey foundational features underlying modern graph query languages. We first discuss two popular graph data models: edge-labelled graphs, where nodes are connected by directed, labelled edges, ...and property graphs, where nodes and edges can further have attributes. Next we discuss the two most fundamental graph querying functionalities: graph patterns and navigational expressions. We start with graph patterns, in which a graph-structured query is matched against the data. Thereafter, we discuss navigational expressions, in which patterns can be matched recursively against the graph to navigate paths of arbitrary length; we give an overview of what kinds of expressions have been proposed and how they can be combined with graph patterns. We also discuss several semantics under which queries using the previous features can be evaluated, what effects the selection of features and semantics has on complexity, and offer examples of such features in three modern languages that are used to query graphs: SPARQL, Cypher, and Gremlin. We conclude by discussing the importance of formalisation for graph query languages; a summary of what is known about SPARQL, Cypher, and Gremlin in terms of expressivity and complexity; and an outline of possible future directions for the area.
We consider the number of independent sets σ(G). In general, the problem of determining the value of σ(G) is NP-complete. For a graph G, the M-S index is defined as the total number of its ...independent sets. In this paper, we mainly discusses the M-S index of two classes of edge corona product graphs, and the specific expressions are given.
This series is devoted to the publication of high-level monographs which cover the whole spectrum of current discrete mathematics and its applications in various fields. One of its main objectives is ...to make available to the professional community expositions of results and foundations of methods that play an important role in both the theory and applications of discrete mathematics.
Interconnections between graph theory and algebraic structure theory have always led to innovative solutions to problems in both areas and new research topics in Mathematics and other scientific ...fields. This reprint aims to emphasize the new theoretical aspects and practical applications of these two research areas. It contains 18 articles selected for publication in the Special Issue "Algebraic Structures and Graph Theory," printed by the MDPI journal Mathematics. The topics addressed by the manuscripts within this reprint cover different aspects principally related to transformation semigroups, Gamma-semigroups, differential graded algebras, BL-algebras, hypergroups and hyperfields, Cayley graphs, graph energy, crossing number, Laplacian spectral radius, hypergraphs, t-graphs, and ideal-based dot total graphs.
Perfect graphs form a well-known class of graphs introduced by Berge in the 1960s in terms of a min–max type equality involving two famous graph parameters. In this work, we survey certain variants ...and subclasses of perfect graphs defined by means of min–max relations of other graph parameters; namely: clique-perfect, coordinated, and neighborhood-perfect graphs. We show the connection between graph classes and both hypergraph theory, the clique graph operator, and some other graph classes. We review different partial characterizations of them by forbidden induced subgraphs, present the previous results, and the main open problems. Computational complexity problems are also discussed.
Knowledge graph reasoning (KGR), aiming to deduce new facts from existing facts based on mined logic rules underlying knowledge graphs (KGs), has become a fast-growing research direction. It has been ...proven to significantly benefit the usage of KGs in many AI applications, such as question answering, recommendation systems, and etc. According to the graph types, existing KGR models can be roughly divided into three categories, i.e. , static models, temporal models, and multi-modal models. Early works in this domain mainly focus on static KGR, and recent works try to leverage the temporal and multi-modal information, which are more practical and closer to real-world. However, no survey papers and open-source repositories comprehensively summarize and discuss models in this important direction. To fill the gap, we conduct a first survey for knowledge graph reasoning tracing from static to temporal and then to multi-modal KGs. Concretely, the models are reviewed based on bi-level taxonomy, i.e. , top-level (graph types) and base-level (techniques and scenarios). Besides, the performances, as well as datasets, are summarized and presented. Moreover, we point out the challenges and potential opportunities to enlighten the readers. The corresponding open-source repository is shared on GitHub https://github.com/LIANGKE23/Awesome-Knowledge-Graph-Reasoning .
PDF
