To see the other types of publications on this topic, follow the link: Graphe complet.

Journal articles on the topic 'Graphe complet'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'Graphe complet.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

1

Potgieter, Zelda. "Lacan’s three orders, the graphe complet and music in film:." Communicare: Journal for Communication Studies in Africa 26, no. 1 (October 20, 2022): 1–26. http://dx.doi.org/10.36615/jcsa.v26i1.1708.

Full text
Abstract:
This article engages with the Lacanian tradition of film theory in order to suggest some of the waysin which music in film may be understood to contribute significantly to subject identification in filmicexperience. Two points are argued: 1) that Lacan’s distinction between the three orders - the Real,the Imaginary and the Symbolic - may usefully be understood in musical terms, and, 2) that thetwo vectors of Lacan’s graphe complet – the vector of speech and the vector of drive – providemeaningful insight into the manner in which the three orders shape filmic musical experience.Analysis of Miklos Rosza’s score for Alfred Hitchcock’s Spellbound (1945) serves to illustrate suchinsights.
APA, Harvard, Vancouver, ISO, and other styles
2

Cappelletti, Luca, Tommaso Fontana, Elena Casiraghi, Vida Ravanmehr, Tiffany J. Callahan, Carlos Cano, Marcin P. Joachimiak, et al. "GRAPE for fast and scalable graph processing and random-walk-based embedding." Nature Computational Science 3, no. 6 (June 26, 2023): 552–68. http://dx.doi.org/10.1038/s43588-023-00465-8.

Full text
Abstract:
AbstractGraph representation learning methods opened new avenues for addressing complex, real-world problems represented by graphs. However, many graphs used in these applications comprise millions of nodes and billions of edges and are beyond the capabilities of current methods and software implementations. We present GRAPE (Graph Representation Learning, Prediction and Evaluation), a software resource for graph processing and embedding that is able to scale with big graphs by using specialized and smart data structures, algorithms, and a fast parallel implementation of random-walk-based methods. Compared with state-of-the-art software resources, GRAPE shows an improvement of orders of magnitude in empirical space and time complexity, as well as competitive edge- and node-label prediction performance. GRAPE comprises approximately 1.7 million well-documented lines of Python and Rust code and provides 69 node-embedding methods, 25 inference models, a collection of efficient graph-processing utilities, and over 80,000 graphs from the literature and other sources. Standardized interfaces allow a seamless integration of third-party libraries, while ready-to-use and modular pipelines permit an easy-to-use evaluation of graph-representation-learning methods, therefore also positioning GRAPE as a software resource that performs a fair comparison between methods and libraries for graph processing and embedding.
APA, Harvard, Vancouver, ISO, and other styles
3

Ismayil, A. Mohamed, and N. Azhagendran. "Isomorphism on Complex Fuzzy Graph." Indian Journal Of Science And Technology 17, SPI1 (April 25, 2024): 86–92. http://dx.doi.org/10.17485/ijst/v17sp1.165.

Full text
Abstract:
Objective: To investigate isomorphism between two complex fuzzy graphs and prove it is an equivalence relation. The major objective of this research paper is to elucidate weak and strong isomorphism, and the study also endeavours to look at the complement of complex fuzzy graphs. Methods: Isomorphism is examined by comparing the membership values of nodes and arcs (both amplitude and phase). The same technique also proves further validation of the equivalence relation, which is also proven by the same technique. This criterion helps us to identify and formalise the isomorphic relationship between complex fuzzy graphs. Findings: This study demonstrates that isomorphism in complex fuzzy graphs allows for consideration of graph structures' differences and similarities. It provides for a better understanding of significant connections between complex fuzzy graphs. Novelty: By offering an elaborate perception of the idea of isomorphism in complex fuzzy graphs, this work advances the discipline. It seeks a better understanding of the complexities of equivalency determination for complicated structures, as well as the application of isomorphism theory to complex fuzzy graphs. Keywords: Complex fuzzy graph, Homomorphism, Isomorphism, Partial order relation, Self complementary
APA, Harvard, Vancouver, ISO, and other styles
4

Hanif, S., K. A. Bhat, and G. Sudhakara. "Complete (2,2) Bipartite Graphs." Malaysian Journal of Mathematical Sciences 16, no. 2 (April 29, 2022): 379–90. http://dx.doi.org/10.47836/mjms.16.2.13.

Full text
Abstract:
A bipartite graph G can be treated as a (1,1) bipartite graph in the sense that, no two vertices in the same part are at distance one from each other. A (2,2) bipartite graph is an extension of the above concept in which no two vertices in the same part are at distance two from each other. In this article, analogous to complete (1,1) bipartite graphs which have the maximum number of pairs of vertices having distance one between them, a complete (2,2) bipartite graph is defined as follows. A complete (2,2) bipartite graph is a graph which is (2,2) bipartite and has the maximum number of pairs of vertices (u,v) such that d(u,v)=2. Such graphs are characterized and their properties are studied. The expressions are derived for the determinant, the permanent and spectral properties of some classes of complete (2,2) bipartite graphs. A class of graphs among complete (2,2) bipartite graphs having golden ratio in their spectrum is obtained.
APA, Harvard, Vancouver, ISO, and other styles
5

Chen, Yuzhong, Zhenyu Liu, Yulin Liu, and Chen Dong. "Distributed Attack Modeling Approach Based on Process Mining and Graph Segmentation." Entropy 22, no. 9 (September 14, 2020): 1026. http://dx.doi.org/10.3390/e22091026.

Full text
Abstract:
Attack graph modeling aims to generate attack models by investigating attack behaviors recorded in intrusion alerts raised in network security devices. Attack models can help network security administrators discover an attack strategy that intruders use to compromise the network and implement a timely response to security threats. However, the state-of-the-art algorithms for attack graph modeling are unable to obtain a high-level or global-oriented view of the attack strategy. To address the aforementioned issue, considering the similarity between attack behavior and workflow, we employ a heuristic process mining algorithm to generate the initial attack graph. Although the initial attack graphs generated by the heuristic process mining algorithm are complete, they are extremely complex for manual analysis. To improve their readability, we propose a graph segmentation algorithm to split a complex attack graph into multiple subgraphs while preserving the original structure. Furthermore, to handle massive volume alert data, we propose a distributed attack graph generation algorithm based on Hadoop MapReduce and a distributed attack graph segmentation algorithm based on Spark GraphX. Additionally, we conduct comprehensive experiments to validate the performance of the proposed algorithms. The experimental results demonstrate that the proposed algorithms achieve considerable improvement over comparative algorithms in terms of accuracy and efficiency.
APA, Harvard, Vancouver, ISO, and other styles
6

DEACONU, VALENTIN, ALEX KUMJIAN, and JOHN QUIGG. "Group actions on topological graphs." Ergodic Theory and Dynamical Systems 32, no. 5 (September 16, 2011): 1527–66. http://dx.doi.org/10.1017/s014338571100040x.

Full text
Abstract:
AbstractWe define the action of a locally compact groupGon a topological graphE. This action induces a natural action ofGon theC*-correspondence ℋ(E) and on the graphC*-algebraC*(E). If the action is free and proper, we prove thatC*(E)⋊rGis strongly Morita equivalent toC*(E/G) . We define the skew product of a locally compact groupGby a topological graphEvia a cocyclec:E1→G. The group acts freely and properly on this new topological graphE×cG. IfGis abelian, there is a dual action onC*(E) such that$C^*(E)\rtimes \hat {G}\cong C^*(E\times _cG)$. We also define the fundamental group and the universal covering of a topological graph.
APA, Harvard, Vancouver, ISO, and other styles
7

Shukla, Samir, Shuchita Goyal, and Anurag Singh. "Homotopy Type of Independence Complexes of Certain Families of Graphs." Contributions to Discrete Mathematics 16, no. 3 (December 31, 2021): 74–92. http://dx.doi.org/10.55016/ojs/cdm.v16i3.71284.

Full text
Abstract:
We show that the independence complexes of generalised Mycielskian of complete graphs are homotopy equivalent to a wedge sum of spheres, and determine the number of copies and the dimensions of these spheres. We also prove that the independence complexes of categorical product of complete graphs are wedge sum of circles, upto homotopy. Further, we show that if we perturb a graph $G$ in a certain way, then the independence complex of this new graph is homotopy equivalent to the suspension of the independence complex of $G$.
APA, Harvard, Vancouver, ISO, and other styles
8

Ji, Shengwei, Chenyang Bu, Lei Li, and Xindong Wu. "Local Graph Edge Partitioning." ACM Transactions on Intelligent Systems and Technology 12, no. 5 (October 31, 2021): 1–25. http://dx.doi.org/10.1145/3466685.

Full text
Abstract:
Graph edge partitioning, which is essential for the efficiency of distributed graph computation systems, divides a graph into several balanced partitions within a given size to minimize the number of vertices to be cut. Existing graph partitioning models can be classified into two categories: offline and streaming graph partitioning models. The former requires global graph information during the partitioning, which is expensive in terms of time and memory for large-scale graphs. The latter creates partitions based solely on the received graph information. However, the streaming model may result in a lower partitioning quality compared with the offline model. Therefore, this study introduces a Local Graph Edge Partitioning model, which considers only the local information (i.e., a portion of a graph instead of the entire graph) during the partitioning. Considering only the local graph information is meaningful because acquiring complete information for large-scale graphs is expensive. Based on the Local Graph Edge Partitioning model, two local graph edge partitioning algorithms—Two-stage Local Partitioning and Adaptive Local Partitioning—are given. Experimental results obtained on 14 real-world graphs demonstrate that the proposed algorithms outperform rival algorithms in most tested cases. Furthermore, the proposed algorithms are proven to significantly improve the efficiency of the real graph computation system GraphX.
APA, Harvard, Vancouver, ISO, and other styles
9

Lu, Jing, Hafiz Mutee-ur-Rehman, Saima Nazeer, and Xuemei An. "The Edge-Weighted Graph Entropy Using Redefined Zagreb Indices." Mathematical Problems in Engineering 2022 (March 28, 2022): 1–12. http://dx.doi.org/10.1155/2022/5958913.

Full text
Abstract:
Measurements of graphs and retrieving structural information of complex networks using degree-based network entropy have become an informational theoretical concept. This terminology is extended by the concept of Shannon entropy. In this paper, we introduce entropy with graphs having edge weights which are basically redefined Zagreb indices. Some bounds are calculated to idealize the performance in limiting different kinds of graph entropy. In addition, we discuss the structural complexity of connected graphs representing chemical structures. In this article, we have discussed the edge-weighted graph entropy with fixed number of vertices, with minimum and maximum degree of a vertex, regular graphs, complete graphs, complete bipartite graphs, and graphs associated with chemical structures.
APA, Harvard, Vancouver, ISO, and other styles
10

R., Hemalatha, and K. Somasundaram. "SOMBOR INDEX OF EDGE CORONA PRODUCT OF SOME CLASSES OF GRAPHS." South East Asian J. of Mathematics and Mathematical Sciences 18, no. 03 (December 30, 2022): 307–16. http://dx.doi.org/10.56827/seajmms.2022.1803.25.

Full text
Abstract:
The operations of graphs spread their wings in designing complex net- work structures in various engineering domains. Graph indices, popularly termed topological indices are computed on the basis of distance or degree. The boundless part of graph indices has its foot print in network centrality and the robustness of complex networks. The goal of this paper is to provide a complete expression for the Sombor index of edge corona product of few classes of graphs.
APA, Harvard, Vancouver, ISO, and other styles
11

Hamidi, Mohammad, and Florentin Smarandache. "Valued-inverse Dombi neutrosophic graph and application." AIMS Mathematics 8, no. 11 (2023): 26614–31. http://dx.doi.org/10.3934/math.20231361.

Full text
Abstract:
<abstract><p>Utilizing two ideas of neutrosophic subsets (NS) and triangular norms, we introduce a new type of graph as valued-inverse Dombi neutrosophic graphs. The valued-inverse Dombi neutrosophic graphs are a generalization of inverse neutrosophic graphs and are dual to Dombi neutrosophic graphs. We present the concepts of (complete) strong valued-inverse Dombi neutrosophic graphs and analyze the complement of (complete) strong valued-inverse Dombi neutrosophic graphs and self-valued complemented valued-inverse Dombi neutrosophic graphs. Since the valued-inverse Dombi neutrosophic graphs depend on real values, solving the non-equation and the concept of homomorphism play a prominent role in determining the complete, strong, complementarity and self-complementarity of valued-inverse Dombi neutrosophic graphs. We introduce the truth membership order, indeterminacy membership order, falsity membership order, truth membership size, indeterminacy membership size and indeterminacy membership size of any given valued-inverse Dombi neutrosophic graph, which play a major role in the application of valued inverse Dombi neutrosophic graphs in complex networks. An application of a valued-inverse Dombi neutrosophic graph is also described in this study.</p></abstract>
APA, Harvard, Vancouver, ISO, and other styles
12

Chaitanya, Ch, and T. V. Pradeep Kumar. "ON THE COMPLETE PRODUCT OF FUZZY GRAPHS." South East Asian J. of Mathematics and Mathematical Sciences 18, no. 02 (September 24, 2022): 185–96. http://dx.doi.org/10.56827/seajmms.2022.1802.17.

Full text
Abstract:
Strong fuzzy graph and complete fuzzy graph are two special kinds of fuzzy graphs in which each edge membership value equals the least of its vertex membership values incidental to the edge. In this research study, we obtain some interesting results on the complete product of a pair of strong fuzzy graphs as well as the complete product of a pair of complete fuzzy graphs. In precise, we prove that the complete product of two strong fuzzy graphs is again a strong fuzzy graph and the complete product of two complete fuzzy graphs is again a complete fuzzy graph. Also, we discuss the conditions under which the property of regularity will be mutually transmitted between the complete product of two fuzzy graphs and one of its factor fuzzy graphs
APA, Harvard, Vancouver, ISO, and other styles
13

Mahalakshmi, L. "Operations on Complex Intuitionistic Fuzzy Graph." International Journal for Research in Applied Science and Engineering Technology 12, no. 3 (March 31, 2024): 527–33. http://dx.doi.org/10.22214/ijraset.2024.58864.

Full text
Abstract:
Abstract: This study introduces the complex intuitionistic fuzzy graphs and analyzes certain fundamental theorem and applications. Further, new ideas in CIFG such as complete complex intuitionistic fuzzy graphs with example. Also, we defined operations on the Direct product, Semi strong product and Strong product of CIFG. Additionally, we presented the density of CIFG and balanced complex intuitionistic fuzzy graph.
APA, Harvard, Vancouver, ISO, and other styles
14

Wu, Yalong, and Haizhen Ren. "Complexity of the Operation Graphs on Cycle and Complete Graph." Journal of Physics: Conference Series 2333, no. 1 (August 1, 2022): 012006. http://dx.doi.org/10.1088/1742-6596/2333/1/012006.

Full text
Abstract:
Abstract The number of spanning trees (or complexity) of a graph can be used to measure the reliabilities of network and circuit design. Although many NP hard problems are related to the complexity of graphs, there are explicit formulas for the complexity of some specific graph classes. This paper mainly studies the explicit expression of the complexity of graphs obtained by graph operations. Through classical graph operations, we obtain some operation graphs generated by cycle and complete graph, and get the closed formulas for the complexity in these operation graphs. Compared with Daoud’s results, we obtain some interesting algebraic properties about the complexity of operation graphs.
APA, Harvard, Vancouver, ISO, and other styles
15

S., Sylvia Vergara. "Complete graph immersions in dense graphs." Discrete Mathematics 340, no. 5 (May 2017): 1019–27. http://dx.doi.org/10.1016/j.disc.2017.01.001.

Full text
APA, Harvard, Vancouver, ISO, and other styles
16

Harris, Haylee Aileen. "The Coloring Graph of Complete Graphs." PUMP Journal of Undergraduate Research 2 (September 6, 2019): 150–60. http://dx.doi.org/10.46787/pump.v2i0.1448.

Full text
Abstract:
We study the coloring graph of the family of complete graphs and we prove that Cn(Kt) is regular, transitive, and connected when n>t. Also, we study whether Cn(Kt) is distance transitive or strongly regular, and find its diameter.
APA, Harvard, Vancouver, ISO, and other styles
17

Ali, Nasir, Zaeema Kousar, Maimoona Safdar, Fikadu Tesgara Tolasa, and Enoch Suleiman. "Mapping Connectivity Patterns: Degree-Based Topological Indices of Corona Product Graphs." Journal of Applied Mathematics 2023 (November 16, 2023): 1–10. http://dx.doi.org/10.1155/2023/8975497.

Full text
Abstract:
Graph theory (GT) is a mathematical field that involves the study of graphs or diagrams that contain points and lines to represent the representation of mathematical truth in a diagrammatic format. From simple graphs, complex network architectures can be built using graph operations. Topological indices (TI) are graph invariants that correlate the physicochemical and interesting properties of different graphs. TI deal with many properties of molecular structure as well. It is important to compute the TI of complex structures. The corona product (CP) of two graphs G and H gives us a new graph obtained by taking one copy of G and V G copies of H and joining the i th vertex of G to every vertex in the i th copy of H . In this paper, based on various CP graphs composed of paths, cycles, and complete graphs, the geometric index (GA) and atom bond connectivity (ABC) index are investigated. Particularly, we discussed the corona products P s ⨀ P t , C t ⨀ C s , K t ⊙ K s , K t ⊙ P s , and P s ⊙ K t and GA and ABC index. Moreover, a few molecular graphs and physicochemical features may be predicted by considering relevant mathematical findings supported by proofs.
APA, Harvard, Vancouver, ISO, and other styles
18

Huang, Xueqin, Xianqiang Zhu, Xiang Xu, Qianzhen Zhang, and Ailin Liang. "Parallel Learning of Dynamics in Complex Systems." Systems 10, no. 6 (December 15, 2022): 259. http://dx.doi.org/10.3390/systems10060259.

Full text
Abstract:
Dynamics always exist in complex systems. Graphs (complex networks) are a mathematical form for describing a complex system abstractly. Dynamics can be learned efficiently from the structure and dynamics state of a graph. Learning the dynamics in graphs plays an important role in predicting and controlling complex systems. Most of the methods for learning dynamics in graphs run slowly in large graphs. The complexity of the large graph’s structure and its nonlinear dynamics aggravate this problem. To overcome these difficulties, we propose a general framework with two novel methods in this paper, the Dynamics-METIS (D-METIS) and the Partitioned Graph Neural Dynamics Learner (PGNDL). The general framework combines D-METIS and PGNDL to perform tasks for large graphs. D-METIS is a new algorithm that can partition a large graph into multiple subgraphs. D-METIS innovatively considers the dynamic changes in the graph. PGNDL is a new parallel model that consists of ordinary differential equation systems and graph neural networks (GNNs). It can quickly learn the dynamics of subgraphs in parallel. In this framework, D-METIS provides PGNDL with partitioned subgraphs, and PGNDL can solve the tasks of interpolation and extrapolation prediction. We exhibit the universality and superiority of our framework on four kinds of graphs with three kinds of dynamics through an experiment.
APA, Harvard, Vancouver, ISO, and other styles
19

Gao, Zhen-Bin, Ricky Guo, Harris Kwong, Sin-Min Lee, and Wei Qiu. "On Vertex-Euclidean Deficiency of Complete Fan Graphs and Complete Wheel Graphs." Journal of Combinatorial Mathematics and Combinatorial Computing 120, no. 1 (June 30, 2024): 399–410. http://dx.doi.org/10.61091/jcmcc120-37.

Full text
Abstract:
A simple graph G with p vertices is said to be vertex-Euclidean if there exists a bijection f : V ( G ) → { 1 , 2 , … , p } such that f ( v 1 ) + f ( v 2 ) > f ( v 3 ) for each C 3 -subgraph with vertex set { v 1 , v 2 , v 3 } , where f ( v 1 ) < f ( v 2 ) < f ( v 3 ) . More generally, the vertex-Euclidean deficiency of a graph G is the smallest integer k such that G ∪ N k is vertex-Euclidean. To illustrate the idea behind this new graph labeling problem, we study the vertex-Euclidean deficiency of two new families of graphs called the complete fan graphs and the complete wheel graphs. We also explore some related problems, and pose several research topics for further study.
APA, Harvard, Vancouver, ISO, and other styles
20

Gao, Zhen-Bin, Ricky Guo, Harris Kwong, Sin-Min Lee, and Wei Qiu. "On Vertex-Euclidean Deficiency of Complete Fan Graphs and Complete Wheel Graphs." Journal of Combinatorial Mathematics and Combinatorial Computing 121, no. 1 (June 30, 2024): 41–52. http://dx.doi.org/10.61091/jcmcc121-04.

Full text
Abstract:
A simple graph G with p vertices is said to be vertex-Euclidean if there exists a bijection f : V ( G ) → { 1 , 2 , … , p } such that f ( v 1 ) + f ( v 2 ) > f ( v 3 ) for each C 3 -subgraph with vertex set { v 1 , v 2 , v 3 } , where f ( v 1 ) < f ( v 2 ) < f ( v 3 ) . More generally, the vertex-Euclidean deficiency of a graph G is the smallest integer k such that G ∪ N k is vertex-Euclidean. To illustrate the idea behind this new graph labeling problem, we study the vertex-Euclidean deficiency of two new families of graphs called the complete fan graphs and the complete wheel graphs. We also explore some related problems, and pose several research topics for further study.
APA, Harvard, Vancouver, ISO, and other styles
21

S, Balakrishnan, Mohamed Ali A, and Rama Murthi K. "A Study on Different types of Product of Anti Fuzzy Graphs." Journal of Computational Mathematica 7, no. 1 (June 30, 2023): 131–38. http://dx.doi.org/10.26524/cm168.

Full text
Abstract:
In this article, we consider to obtain new anti fuzzy graph from given anti fuzzy graphs. Product of anti fuzzy graphs is an operation on anti fuzzy graphs that produce new anti fuzzy graph. We consider tensor, normal, modular anti fuzzy graphs products, which are adapted from fuzzy graphs products. In general, product of any two anti fuzzy graphs is an anti fuzzy graph. Product of any two strong anti fuzzy graphs is an anti fuzzy graph strong. Normal product of two anti fuzzy graph complete is a complete anti fuzzy graph. Other than that, different of anti fuzzy products are also discussed.
APA, Harvard, Vancouver, ISO, and other styles
22

Itzhakov, Avraham, and Michael Codish. "Incremental Symmetry Breaking Constraints for Graph Search Problems." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 02 (April 3, 2020): 1536–43. http://dx.doi.org/10.1609/aaai.v34i02.5513.

Full text
Abstract:
This paper introduces incremental symmetry breaking constraints for graph search problems which are complete and compact. We show that these constraints can be computed incrementally: A symmetry breaking constraint for order n graphs can be extended to one for order n + 1 graphs. Moreover, these constraints induce a special property on their canonical solutions: An order n canonical graph contains a canonical subgraph on the first k vertices for every 1 ≤ k ≤ n. This facilitates a “generate and extend” paradigm for parallel graph search problem solving: To solve a graph search problem φ on order n graphs, first generate the canonical graphs of some order k < n. Then, compute canonical solutions for φ by extending, in parallel, each canonical order k graph together with suitable symmetry breaking constraints. The contribution is that the proposed symmetry breaking constraints enable us to extend the order k canonical graphs to order n canonical solutions. We demonstrate our approach through its application on two hard graph search problems.
APA, Harvard, Vancouver, ISO, and other styles
23

Basavanagoud, B., and Roopa S. Kusugal. "On the Line Degree Splitting Graph of a Graph." Bulletin of Mathematical Sciences and Applications 18 (May 2017): 1–10. http://dx.doi.org/10.18052/www.scipress.com/bmsa.18.1.

Full text
Abstract:
In this paper, we introduce the concept of the line degree splitting graph of a graph. We obtain some properties of this graph. We find the girth of the line degree splitting graphs. Further, we establish the characterization of graphs whose line degree splitting graphs are eulerian, complete bipartite graphs and complete graphs.
APA, Harvard, Vancouver, ISO, and other styles
24

Feng, Yun, and Wensong Lin. "Some Results on the Erdős–Faber–Lovász Conjecture." Symmetry 14, no. 7 (June 27, 2022): 1327. http://dx.doi.org/10.3390/sym14071327.

Full text
Abstract:
Erdős–Faber–Lovász conjecture states that if a graph G is a union of the n edge-disjoint copies of complete graph Kn, that is, each pair of complete graphs has at most one shared vertex, then the chromatic number of graph G is n. In fact, we only need to consider the graphs where each pair of complete graphs has exactly one shared vertex. However, each shared vertex may be shared by more than two complete graphs. Therefore, this paper first considers the graphs where each shared vertex happens to be shared by two complete graphs, and then discusses the graphs with only one shared vertex shared by more than two complete graphs. The conjecture is correct for these two kinds of graphs in this work. Finally, the graph where each shared vertex happens to be shared by three complete graphs has been studied, and the conjecture also holds for such graphs when n=13. The graphs discussed in this paper have certain symmetric properties. The symmetry of graphs plays an important role in coloring. This work is an attempt to combine the symmetry of graphs with the coloring of graphs.
APA, Harvard, Vancouver, ISO, and other styles
25

SUN, YACHYANG, and KOK-HOO YEAP. "EDGE COVERING OF COMPLEX TRIANGLES IN RECTANGULAR DUAL FLOORPLANNING." Journal of Circuits, Systems and Computers 03, no. 03 (September 1993): 721–31. http://dx.doi.org/10.1142/s0218126693000435.

Full text
Abstract:
Rectangular dual graph approach to floorplanning is based on the adjacency graph of the modules in a floorplan. If the input adjacency graph contains a cycle of length three which is not a face (complex triangle), a rectangular floorplan does not exist. Thus, complex triangles have to be eliminated before applying any floorplanning algorithm. This paper shows that the weighted complex triangle elimination problem is NP-complete, even when the input graphs are restricted to 1-level containment. For adjacency graph with 0-level containment, the unweighted problem is optimally solvable in O(c1.5 + n) time where c is the number of complex triangles and n is the number of vertices of the input graph.
APA, Harvard, Vancouver, ISO, and other styles
26

Wenni, Mariza. "BILANGAN KROMATIK LOKASI DARI GRAF P m P n ; K m P n ; DAN K , m K n." Jurnal Matematika UNAND 2, no. 1 (March 10, 2013): 14. http://dx.doi.org/10.25077/jmu.2.1.14-22.2013.

Full text
Abstract:
Let G and H be two connected graphs. Let c be a vertex k-coloring of aconnected graph G and let = fCg be a partition of V (G) into the resultingcolor classes. For each v 2 V (G), the color code of v is dened to be k-vector: c1; C2; :::; Ck(v) =(d(v; C1); d(v; C2); :::; d(v; Ck)), where d(v; Ci) = minfd(v; x) j x 2 Cg, 1 i k. Ifdistinct vertices have distinct color codes with respect to , then c is called a locatingcoloring of G. The locating chromatic number of G is the smallest natural number ksuch that there are locating coloring with k colors in G. The Cartesian product of graphG and H is a graph with vertex set V (G) V (H), where two vertices (a; b) and (a)are adjacent whenever a = a0and bb02 E(H), or aa0i2 E(G) and b = b, denotedby GH. In this paper, we will study about the locating chromatic numbers of thecartesian product of two paths, the cartesian product of paths and complete graphs, andthe cartesian product of two complete graphs.
APA, Harvard, Vancouver, ISO, and other styles
27

Chen, Fukun, Guisheng Yin, Yuxin Dong, Gesu Li, and Weiqi Zhang. "KHGCN: Knowledge-Enhanced Recommendation with Hierarchical Graph Capsule Network." Entropy 25, no. 4 (April 20, 2023): 697. http://dx.doi.org/10.3390/e25040697.

Full text
Abstract:
Knowledge graphs as external information has become one of the mainstream directions of current recommendation systems. Various knowledge-graph-representation methods have been proposed to promote the development of knowledge graphs in related fields. Knowledge-graph-embedding methods can learn entity information and complex relationships between the entities in knowledge graphs. Furthermore, recently proposed graph neural networks can learn higher-order representations of entities and relationships in knowledge graphs. Therefore, the complete presentation in the knowledge graph enriches the item information and alleviates the cold start of the recommendation process and too-sparse data. However, the knowledge graph’s entire entity and relation representation in personalized recommendation tasks will introduce unnecessary noise information for different users. To learn the entity-relationship presentation in the knowledge graph while effectively removing noise information, we innovatively propose a model named knowledge—enhanced hierarchical graph capsule network (KHGCN), which can extract node embeddings in graphs while learning the hierarchical structure of graphs. Our model eliminates noisy entities and relationship representations in the knowledge graph by the entity disentangling for the recommendation and introduces the attentive mechanism to strengthen the knowledge-graph aggregation. Our model learns the presentation of entity relationships by an original graph capsule network. The capsule neural networks represent the structured information between the entities more completely. We validate the proposed model on real-world datasets, and the validation results demonstrate the model’s effectiveness.
APA, Harvard, Vancouver, ISO, and other styles
28

Malik, M. Aslam, and M. Khalid Mahmood. "On Simple Graphs Arising from Exponential Congruences." Journal of Applied Mathematics 2012 (2012): 1–10. http://dx.doi.org/10.1155/2012/292895.

Full text
Abstract:
We introduce and investigate a new class of graphs arrived from exponential congruences. For each pair of positive integersaandb, letG(n)denote the graph for whichV={0,1,…,n−1}is the set of vertices and there is an edge betweenaandbif the congruenceax≡b (mod n)is solvable. Letn=p1k1p2k2⋯prkrbe the prime power factorization of an integern, wherep1<p2<⋯<prare distinct primes. The number of nontrivial self-loops of the graphG(n)has been determined and shown to be equal to∏i=1r(ϕ(piki)+1). It is shown that the graphG(n)has2rcomponents. Further, it is proved that the componentΓpof the simple graphG(p2)is a tree with root at zero, and ifnis a Fermat's prime, then the componentΓϕ(n)of the simple graphG(n)is complete.
APA, Harvard, Vancouver, ISO, and other styles
29

El-Mesady, A., and Omar Bazighifan. "Decompositions of Circulant-Balanced Complete Multipartite Graphs Based on a Novel Labelling Approach." Journal of Function Spaces 2022 (July 18, 2022): 1–17. http://dx.doi.org/10.1155/2022/2017936.

Full text
Abstract:
For applied scientists and engineers, graph theory is a strong and vital tool for evaluating and inventing solutions for a variety of issues. Graph theory is extremely important in complex systems, particularly in computer science. Many scientific areas use graph theory, including biological sciences, engineering, coding, and operational research. A strategy for the orthogonal labelling of a bipartite graph G with n edges has been proposed in the literature, yielding cyclic decompositions of balanced complete bipartite graphs K n , n by the graph G . A generalization to circulant-balanced complete multipartite graphs K n , n , ⋯ , n ⏟ m ; m , n ≥ 2 , is our objective here. In this paper, we expand the orthogonal labelling approach used to generate cyclic decompositions for K n , n to a generalized orthogonal labelling approach that may be used for decomposing K n , n , ⋯ , n ⏟ m . We can decompose K n , n , ⋯ , n ⏟ m into distinct graph classes based on the proposed generalized orthogonal labelling approach.
APA, Harvard, Vancouver, ISO, and other styles
30

Li, Yanying. "Characterizing the Minimal Essential Graphs of Maximal Ancestral Graphs." International Journal of Pattern Recognition and Artificial Intelligence 34, no. 04 (August 5, 2019): 2059009. http://dx.doi.org/10.1142/s0218001420590090.

Full text
Abstract:
Learning ancestor graph is a typical NP-hard problem. We consider the problem to represent a Markov equivalence class of ancestral graphs with a compact representation. Firstly, the minimal essential graph is defined to represent the equivalent class of maximal ancestral graphs with the minimum number of invariant arrowheads. Then, an algorithm is proposed to learn the minimal essential graph of ancestral graphs based on the detection of minimal collider paths. It is the first algorithm to use necessary and sufficient conditions for Markov equivalence as a base to seek essential graphs. Finally, a set of orientation rules is presented to orient edge marks of a minimal essential graph. Theory analysis shows our algorithm is sound, and complete in the sense of recognizing all minimal collider paths in a given ancestral graph. And the experiment results show we can discover all invariant marks by these orientation rules.
APA, Harvard, Vancouver, ISO, and other styles
31

Belardo, Francesco, Maurizio Brunetti, and Suliman Khan. "NEPS of complex unit gain graphs." Electronic Journal of Linear Algebra 39 (December 9, 2023): 621–43. http://dx.doi.org/10.13001/ela.2023.8015.

Full text
Abstract:
A complex unit gain graph (or $\mathbb T$-gain graph) is a gain graph with gains in $\mathbb T$, the multiplicative group of complex units. Extending a classical construction for simple graphs due to Cvektovic, suitably defined noncomplete extended $p$-sums (NEPS, for short) of $\mathbb T$-gain graphs are considered in this paper. Structural properties of NEPS like balance and some spectral properties and invariants of their adjacency and Laplacian matrices are investigated, including the energy and the possible symmetry of the adjacency spectrum. It is also shown how NEPS are useful to obtain infinitely many integral graphs from the few at hands.Moreover, it is studied how NEPS of $\mathbb T$-gain graphs behave with respect to the property of being nut, i.e., having $0$ as simple adjacency eigenvalue and nowhere zero $0$-eigenvectors. Finally, a family of new products generalizing NEPS is introduced, and their few first spectral properties explored.
APA, Harvard, Vancouver, ISO, and other styles
32

BRYANT, DARRYN, and BARBARA MAENHAUT. "COMMON MULTIPLES OF COMPLETE GRAPHS." Proceedings of the London Mathematical Society 86, no. 2 (March 2003): 302–26. http://dx.doi.org/10.1112/s0024611502013771.

Full text
Abstract:
A graph $H$ is said to divide a graph $G$ if there exists a set $S$ of subgraphs of $G$, all isomorphic to $H$, such that the edge set of $G$ is partitioned by the edge sets of the subgraphs in $S$. Thus, a graph $G$ is a common multiple of two graphs if each of the two graphs divides $G$. This paper considers common multiples of a complete graph of order $m$ and a complete graph of order $n$. The complete graph of order $n$ is denoted $K_n$. In particular, for all positive integers $n$, the set of integers $q$ for which there exists a common multiple of $K_3$ and $K_n$ having precisely $q$ edges is determined.It is shown that there exists a common multiple of $K_3$ and $K_n$ having $q$ edges if and only if $q \equiv 0 \, ({\rm mod}\, 3)$, $q \equiv 0 \, ({\rm mod}\, \binom n2)$ and(1) $q \neq 3 \binom n2$ when $n \equiv 5 \, ({\rm mod}\, 6)$; (2) $q \geq (n + 1) \binom n2$ when $n$ is even; (3) $q \notin \{36, 42, 48\}$ when $n = 4$.The proof of this result uses a variety of techniques including the use of Johnson graphs, Skolem and Langford sequences, and equitable partial Steiner triple systems.2000 Mathematical Subject Classification: 05C70, 05B30, 05B07.
APA, Harvard, Vancouver, ISO, and other styles
33

Wang, Jinhua, and Dengju Ma. "Petersen Graph Decompositions of Complete Multipartite Graphs." Graphs and Combinatorics 26, no. 5 (March 5, 2010): 737–44. http://dx.doi.org/10.1007/s00373-010-0925-x.

Full text
APA, Harvard, Vancouver, ISO, and other styles
34

Erdős, P., and L. Pyber. "Covering a graph by complete bipartite graphs." Discrete Mathematics 170, no. 1-3 (June 1997): 249–51. http://dx.doi.org/10.1016/s0012-365x(96)00124-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
35

Siddique, Saba, Uzma Ahmad, Wardat us Salam, Muhammad Akram, and Florentin Smarandache. "Representation of competitions by complex neutrosophic information." Journal of Intelligent & Fuzzy Systems 39, no. 5 (November 19, 2020): 7881–97. http://dx.doi.org/10.3233/jifs-201338.

Full text
Abstract:
The concept of generalized complex neutrosophic graph of type 1 is an extended approach of generalized neutrosophic graph of type 1. It is an effective model to handle inconsistent information of periodic nature. In this research article, we discuss certain notions, including isomorphism, competition graph, minimal graph and competition number corresponding to generalized complex neutrosophic graphs. Further, we describe these concepts by several examples and present some of their properties. Moreover, we analyze that a competition graph corresponding to a generalized complex neutrosophic graph can be represented by an adjacency matrix with suitable real life examples. Also, we enumerate the utility of generalized complex neutrosophic competition graphs for computing the strength of competition between the objects. Finally, we highlight the significance of our proposed model by comparative analysis with the already existing models.
APA, Harvard, Vancouver, ISO, and other styles
36

Muntyan, Evgenia R. "Knowledge representation in graph-models of complex technical systems." Informatization and communication, no. 3 (May 5, 2020): 12–16. http://dx.doi.org/10.34219/2078-8320-2020-11-3-12-16.

Full text
Abstract:
The article analyzes a number of methods of knowledge formation using various graph models, including oriented, undirected graphs with the same type of edges and graphs with multiple and different types of edges. This article shows the possibilities of using graphs to represent a three-level structure of knowledge in the field of complex technical systems modeling. In such a model, at the first level, data is formed in the form of unrelated graph vertices, at the second level – information presented by a related undirected graph, and at the third level – knowledge in the form of a set of graph paths. The proposed interpretation of the structure of knowledge allows to create new opportunities for analytical study of knowledge and information, their properties and relationships.
APA, Harvard, Vancouver, ISO, and other styles
37

El-Shanawany, R. A., and M. Sh Higazy. "General Symmetric Starter of Orthogonal Double Covers of Complete Bipartite Graph." International Journal of Mathematics and Mathematical Sciences 2007 (2007): 1–8. http://dx.doi.org/10.1155/2007/42892.

Full text
Abstract:
An orthogonal double cover (ODC) of the complete graph is a collection of graphs such that every two of them share exactly one edge and every edge of the complete graph belongs to exactly two of the graphs. In this paper, we consider the case where the graph to be covered twice is the complete bipartite graphKmn,mn(for any values ofm,n) and all graphs in the collection are isomorphic to certain spanning subgraphs. Furthermore, the ODCs ofKn,nby certain disjoint stars are constructed.
APA, Harvard, Vancouver, ISO, and other styles
38

Duan, Huiming, and Yonghong Li. "On Connected m-HPK(n1,n2,n3,n4)[Kt]-Residual Graphs." Journal of Discrete Mathematics 2013 (March 12, 2013): 1–7. http://dx.doi.org/10.1155/2013/983830.

Full text
Abstract:
We define m-HPK(n1,n2,n3,n4)[Kt]-residual graphs in which HPK is a hyperplane complete graph. We extend P. Erdös, F. Harary, and M. Klawe's definition of plane complete residual graph to hyperplane and obtain the hyperplane complete residual graph. Further, we obtain the minimum order of HPK(n1,n2,n3,n4)[Kt]-residual graphs and m-HPK(n1,n2,n3,n4)[Kt]-residual graphs. In addition, we obtain a unique minimal HPK(n1,n2,n3,n4)[Kt]-residual graphs and a unique minimal m-HPK(n1,n2,n3,n4)[Kt]-residual graphs.
APA, Harvard, Vancouver, ISO, and other styles
39

LI, YANG, JIAHU QIN, FENGCHUN LEI, XIANGKE WANG, and XIHAI ZHANG. "TRIANGLE-Y EXCHANGES ON INTRINSIC KNOTTING OF ALMOST COMPLETE AND COMPLETE PARTITE GRAPHS." Journal of Knot Theory and Its Ramifications 21, no. 04 (April 2012): 1250034. http://dx.doi.org/10.1142/s021821651100990x.

Full text
Abstract:
Let G be a 0- or 1-deficient graph which is intrinsically knotted, let J represent any graph obtained from G by a finite sequence of Δ-Y exchanges and/or vertex expansions. We prove that removing any vertex of J, and all edges incident to that vertex, yields an intrinsically linked graph. This result provides more intrinsically knotted graphs which satisfy the conjecture mentioned in Adams' The Knot Book that removing any vertex from an intrinsically knotted graph yields an intrinsically linked graph.
APA, Harvard, Vancouver, ISO, and other styles
40

Razumovsky, P. V., and M. B. Abrosimov. "THE MINIMAL VERTEX EXTENSIONS FOR COLORED COMPLETE GRAPHS." Bulletin of the South Ural State University series "Mathematics. Mechanics. Physics" 13, no. 4 (2021): 77–89. http://dx.doi.org/10.14529/mmph210409.

Full text
Abstract:
The article proposes the results of the search for minimal vertex extensions of undirected colored complete graphs. The research topic is related to the modelling of full fault tolerant technical systems with a different type of their objects in the terminology of graph theory. Let a technical system be Σ, then there is a graph G(Σ), which vertices reflects system’s objects and edges reflects connections between these objects. Type of each object reflected in a mapping of some color from F = {1,2…,i} to the corresponding vertex. System’s Σ vertex extension is a graph G(Σ) which contains additional vertices. System reflected by graph G(Σ) can work even if there are k faults of its objects. Complete graph is a graph where each two vertices have an edge between them. Complete graphs have no edge extensions because there is no way to add additional edge to the graph with a maximum number of edges. In other words, the system reflected by some complete graph cannot be able to resist connection faults. Therefore the article research is focused on vertex extensions only. There is a description of vertex extensions existence condition for those colored complete graphs. This paper considers generating schemes for such minimal vertex extensions along with formulas, which allows to calculate number of additional edges to have an ability to construct minimal vertex extension.
APA, Harvard, Vancouver, ISO, and other styles
41

Kolotoglu, Emre. "A complete solution to the spectrum problem for graphs with six vertices and up to nine edges." Contributions to Discrete Mathematics 15, no. 3 (December 22, 2020): 1–24. http://dx.doi.org/10.55016/ojs/cdm.v15i3.62290.

Full text
Abstract:
Let $G$ be a graph. A $G$-design of order $n$ is a decomposition of the complete graph $K_n$ into disjoint copies of $G$. The existence problem of graph designs has been completely solved for all graphs with up to five vertices, and all graphs with six vertices and up to seven edges; and almost completely solved for all graphs with six vertices and eight edges leaving two cases of order 32 unsettled. Up to isomorphism there are 20 graphs with six vertices and nine edges (and no isolated vertex). The spectrum problem has been solved completely for 11 of these graphs, and partially for 2 of these graphs. In this article, the two missing graph designs for the six-vertex eight-edge graphs are constructed, and a complete solution to the spectrum problem for the six-vertex nine-edge graphs is given; completing the spectrum problem for all graphs with six vertices and up to nine edges.
APA, Harvard, Vancouver, ISO, and other styles
42

Lazzarin, João Roberto, Oscar Franscisco Másquez Sosa, and Fernando Colman Tura. "Q-borderenergetic threshold graphs." Ciência e Natura 42 (June 29, 2020): e91. http://dx.doi.org/10.5902/2179460x39755.

Full text
Abstract:
A graph G is said to be borderenergetic (L-borderenergetic, respectively) if its energy (Laplacian energy, respectively) equals the energy (Laplacian energy, respectively) of the complete graph. Recently, this concept was extend to signless Laplacian energy (see Tao, Q., Hou, Y. (2018). Q-borderenergetic graphs. AKCE International Journal of Graphs and Combinatorics). A graph G is called Q-borderenergetic if its signless Laplacian energy is the same of the complete graph Kn; i.e., QE(G) = QE(Kn) = 2n - 2: In this paper, we investigate Q-borderenergetic graphs on the class of threshold graphs. For a family of threshold graphs of order n = 100; we find out exactly 13 graphs such that QE(G) = 2n- 2:
APA, Harvard, Vancouver, ISO, and other styles
43

SHARMA, ROHAN, BIBHAS ADHIKARI, and TYLL KRUEGER. "SELF-ORGANIZED CORONA GRAPHS: A DETERMINISTIC COMPLEX NETWORK MODEL WITH HIERARCHICAL STRUCTURE." Advances in Complex Systems 22, no. 06 (September 2019): 1950019. http://dx.doi.org/10.1142/s021952591950019x.

Full text
Abstract:
In this paper, we propose a self-organization mechanism for newly appeared nodes during the formation of corona graphs that define a hierarchical pattern in the resulting corona graphs and we call it self-organized corona graphs (SoCG). We show that the degree distribution of SoCG follows power-law in its tail with power-law exponent approximately 2. We also show that the diameter is less equal to 4 for SoCG defined by any seed graph and for certain seed graphs, the diameter remains constant during its formation. We derive lower bounds of clustering coefficients of SoCG defined by certain seed graphs. Thus, the proposed SoCG can be considered as a growing network generative model which is defined by using the corona graphs and a self-organization process such that the resulting graphs are scale-free small-world highly clustered growing networks. The SoCG defined by a seed graph can also be considered as a network with a desired motif which is the seed graph itself.
APA, Harvard, Vancouver, ISO, and other styles
44

Laomala, Janejira, Keaitsuda Maneeruk Nakprasit, Kittikorn Nakprasit, and Watcharintorn Ruksasakchai. "The Strong Equitable Vertex 1-Arboricity of Complete Bipartite Graphs and Balanced Complete k-Partite Graphs." Symmetry 14, no. 2 (January 31, 2022): 287. http://dx.doi.org/10.3390/sym14020287.

Full text
Abstract:
An equitable k-coloring of a graph G is a proper k-coloring of G such that the sizes of any two color classes differ by at most one. An equitable (q,r)-tree-coloring of a graph G is an equitable q-coloring of G such that the subgraph induced by each color class is a forest of maximum degree at most r. Let the strong equitable vertex r-arboricity of a graph G, denoted by var≡(G), be the minimum p such that G has an equitable (q,r)-tree-coloring for every q≥p. The values of va1≡(Kn,n) were investigated by Tao and Lin and Wu, Zhang, and Li where exact values of va1≡(Kn,n) were found in some special cases. In this paper, we extend their results by giving the exact values of va1≡(Kn,n) for all cases. In the process, we introduce a new function related to an equitable coloring and obtain a more general result by determining the exact value of each va1≡(Km,n) and va1≡(G) where G is a balanced complete k-partite graph Kn,…,n. Both complete bipartite graphs Km,n and balanced complete k-partite graphs Kn,…,n are symmetry in several aspects and also studied broadly. For the other aspect of symmetry, by the definition of equitable k-coloring of graphs, in a specific case that the number of colors divides the number of vertices of graph, we can say that the graph is a balanced k-partite graph.
APA, Harvard, Vancouver, ISO, and other styles
45

Ghazwani, Haleemah, Muhammad Faisal Nadeem, Faiza Ishfaq, and Ali N. A. Koam. "On Entropy of Some Fractal Structures." Fractal and Fractional 7, no. 5 (April 30, 2023): 378. http://dx.doi.org/10.3390/fractalfract7050378.

Full text
Abstract:
Shannon entropy, also known as information entropy or entropy, measures the uncertainty or randomness of probability distribution. Entropy is measured in bits, quantifying the average amount of information required to identify an event from the distribution. Shannon’s entropy theory initiates graph entropies and develops information-theoretic magnitudes for structural computational evidence of organic graphs and complex networks. Graph entropy measurements are valuable in several scientific fields, such as computing, chemistry, biology, and discrete mathematics. In this study, we investigate the entropy of fractal-type networks by considering cycle, complete, and star networks as base graphs using degree-based topological indices.
APA, Harvard, Vancouver, ISO, and other styles
46

Li, Qiuping, and Liangwen Tang. "Infinite Numbers of Infinite Classes L-Borderenergetic Graphs." Match - Communications in Mathematical and in Computer Chemistry 90, no. 3 (July 2023): 729–42. http://dx.doi.org/10.46793/match.90-3.729l.

Full text
Abstract:
The graph G of order n is an L-borderenergetic graph which means it has the same Laplacian energy as the complete graph Kn. In this paper, we find that the combination of complete bipartite graphs and stars can construct infinite numbers of infinite classes L-borderenergetic graphs. We give two infinite numbers of infinite classes L-borderenergetic graphs and two infinite classes Lborderenergetic graphs under the operators union, join and their mixed. This research could provide experience for further study the structural characteristics of L-borderenergetic graphs.
APA, Harvard, Vancouver, ISO, and other styles
47

Osztényi, József. "A study of the neighborhood complex of $-stable Kneser graphs." Gradus 8, no. 3 (2021): 179–86. http://dx.doi.org/10.47833/2021.3.csc.006.

Full text
Abstract:
In 1978, Alexander Schrijver defined the stable Kneser graphs as a vertex critical subgraphs of the Kneser graphs. In the early 2000s, Günter M. Ziegler generalized Schrijver’s construction and defined the s-stable Kneser graphs. Thereafter Frédéric Meunier determined the chromatic number of the s-stable Kneser graphs for special cases and formulated a conjecture on the chromatic number of the s-stable Kneser graphs. In this paper we study a generalization of the s-stable Kneser graphs. For some specific values of the parameter we show that the neighborhood complex of < s, t >-stable Kneser graph has the same homotopy type as the (t − 1)-sphere. In particular, this implies that the chromatic number of this graph is t + 1.
APA, Harvard, Vancouver, ISO, and other styles
48

Ibarra, Sofía, and Luis Manuel Rivera. "The automorphism groups of some token graphs." Proyecciones (Antofagasta) 42, no. 6 (December 1, 2023): 1627–51. http://dx.doi.org/10.22199/issn.0717-6279-5954.

Full text
Abstract:
The token graphs of graphs have been studied at least from the 80’s with different names and by different authors. The Johnson graph J(n, k) is isomorphic to the k-token graph of the complete graph Kn. To our knowledge, the unique results about the automorphism groups of token graphs are for the case of the Johnson graphs. In this paper we begin the study of the automorphism groups of token graphs of another graphs. In particular we obtain the automorphism group of the k-token graph of the path graph Pn, for n 6≠ 2k. Also, we obtain the automorphism group of the 2-token graph of the following graphs: cycle, star, fan and wheel graphs.
APA, Harvard, Vancouver, ISO, and other styles
49

Gu, Zhendong, Shuming Zhou, Jiafei Liu, Qianru Zhou, and Dajin Wang. "Shapley Distance and Shapley Index for Some Special Graphs." Parallel Processing Letters 30, no. 04 (December 2020): 2050012. http://dx.doi.org/10.1142/s0129626420500127.

Full text
Abstract:
The Shapley distance in a graph is defined based on Shapley value in cooperative game theory. It is used to measure the cost for a vertex in a graph to access another vertex. In this paper, we establish the Shapley distance between two arbitrary vertices for some special graphs, i.e., path, tree, cycle, complete graph, complete bipartite, and complete multipartite graph. Moreover, based on the Shapley distance, we propose a new index, namely Shapley index, and then compare Shapley index with Wiener index and Kirchhoff index for these special graphs. We also characterize the extremal graphs in which these three indices are equal.
APA, Harvard, Vancouver, ISO, and other styles
50

ANGELES-CANUL, RICARDO JAVIER, RACHAEL M. NORTON, MICHAEL C. OPPERMAN, CHRISTOPHER C. PARIBELLO, MATTHEW C. RUSSELL, and CHRISTINO TAMON. "QUANTUM PERFECT STATE TRANSFER ON WEIGHTED JOIN GRAPHS." International Journal of Quantum Information 07, no. 08 (December 2009): 1429–45. http://dx.doi.org/10.1142/s0219749909006103.

Full text
Abstract:
This paper studies quantum perfect state transfer on weighted graphs. We prove that the join of a weighted two-vertex graph with any regular graph has perfect state transfer. This generalizes a result of Casaccino et al.1 where the regular graph is a complete graph with or without a missing edge. In contrast, we prove that the half-join of a weighted two-vertex graph with any weighted regular graph has no perfect state transfer. As a corollary, unlike for complete graphs, adding weights in complete bipartite graphs does not produce perfect state transfer. We also observe that any Hamming graph has perfect state transfer between each pair of its vertices. The result is a corollary of a closure property on weighted Cartesian products of perfect state transfer graphs. Moreover, on a hypercube, we show that perfect state transfer occurs between uniform superpositions on pairs of arbitrary subcubes, thus generalizing results of Bernasconi et al.2 and Moore and Russell.3
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography