Log in

Relevant bibliographies by topics / Graphe simple / Journal articles

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

Journal articles on the topic 'Graphe simple'

Author: Grafiati

Published: 18 May 2024

Last updated: 8 June 2024

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 simple.'

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

Hudry, Olivier. "Application of the “descent with mutations” metaheuristic to a clique partitioning problem." RAIRO - Operations Research 53, no. 3 (July 2019): 1083–95. http://dx.doi.org/10.1051/ro/2018048.

Full text

Abstract:

We study here the application of the “descent with mutations” metaheuristic to a problem arising from the field of classification and cluster analysis (dealing more precisely with the aggregation of symmetric relations) and which can be represented as a clique partitioning of a weighted graph. In this problem, we deai with a complete undirected graphe G; the edges of G have weights which can be positive, negative or equal to 0; the aim is to partition the vertices of G into disjoint cliques (whose number depends on G in order to minimize the sum of the weights of the edges with their two extremities in a same clique; this problem is NP-hard. The “descent with mutations” is a local search metaheuristic, of which the design is very simple and is based on local transformation. It consists in randomly performing random elementary transformations, irrespective improvement or worsening with respect to the objective function. We compare it with another very efficient metaheuristic, which is a simulated annealing method improved by the addition of some ingredients coming from the noising methods. Experiments show that the descent with mutations is at least as efficient for the studied problem as this improved simulated annealing, usually a little better, while it is much easier to design and to tune.

APA, Harvard, Vancouver, ISO, and other styles

2

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

3

Voorhees, Burton, and Alex Murray. "Fixation probabilities for simple digraphs." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 469, no. 2154 (June 8, 2013): 20120676. http://dx.doi.org/10.1098/rspa.2012.0676.

Full text

Abstract:

The problem of finding birth–death fixation probabilities for configurations of normal and mutants on an N -vertex graph is formulated in terms of a Markov process on the 2 N -dimensional state space of possible configurations. Upper and lower bounds on the fixation probability after any given number of iterations of the birth–death process are derived in terms of the transition matrix of this process. Consideration is then specialized to a family of graphs called circular flows, and we present a summation formula for the complete bipartite graph, giving the fixation probability for an arbitrary configuration of mutants in terms of a weighted sum of the single-vertex fixation probabilities. This also yields a closed-form solution for the fixation probability of bipartite graphs. Three entropy measures are introduced, providing information about graph structure. Finally, a number of examples are presented, illustrating cases of graphs that enhance or suppress fixation probability for fitness r >1 as well as graphs that enhance fixation probability for only a limited range of fitness. Results are compared with recent results reported in the literature, where a positive correlation is observed between vertex degree variance and fixation probability for undirected graphs. We show a similar correlation for directed graphs, with correlation not directly to fixation probability but to the difference between fixation probability for a given graph and a complete graph.

APA, Harvard, Vancouver, ISO, and other styles

4

Azari, M., and A. Iranmanesh. "On the edge-Wiener index of the disjunctive product of simple graphs." Algebra and Discrete Mathematics 30, no. 1 (2020): 1–14. http://dx.doi.org/10.12958/adm242.

Full text

Abstract:

The edge-Wiener index of a simple connected graph G is defined as the sum of distances between all pairs of edges of G where the distance between two edges in G is the distance between the corresponding vertices in the line graph of G. In this paper, we study the edge-Wiener index under the disjunctive product of graphs and apply our results to compute the edge-Wiener index for the disjunctive product of paths and cycles.

APA, Harvard, Vancouver, ISO, and other styles

5

Ali, Akbar. "Tetracyclic graphs with maximum second Zagreb index: A simple approach." Asian-European Journal of Mathematics 11, no. 05 (October 2018): 1850064. http://dx.doi.org/10.1142/s179355711850064x.

Full text

Abstract:

In the chemical graph theory, graph invariants are usually referred to as topological indices. The second Zagreb index (denoted by [Formula: see text]) is one of the most studied topological indices. For [Formula: see text], let [Formula: see text] be the collection of all non-isomorphic connected graphs with [Formula: see text] vertices and [Formula: see text] edges (such graphs are known as tetracyclic graphs). Recently, Habibi et al. [Extremal tetracyclic graphs with respect to the first and second Zagreb indices, Trans. on Combin. 5(4) (2016) 35–55.] characterized the graph having maximum [Formula: see text] value among all members of the collection [Formula: see text]. In this short note, an alternative but relatively simple approach is used for characterizing the aforementioned graph.

APA, Harvard, Vancouver, ISO, and other styles

6

Vasanthi, R., and K. Subramanian. "On Vertex Covering Transversal Domination Number of Regular Graphs." Scientific World Journal 2016 (2016): 1–7. http://dx.doi.org/10.1155/2016/1029024.

Full text

Abstract:

A simple graphG=(V,E)is said to ber-regular if each vertex ofGis of degreer. The vertex covering transversal domination numberγvct(G)is the minimum cardinality among all vertex covering transversal dominating sets ofG. In this paper, we analyse this parameter on different kinds of regular graphs especially forQnandH3,n. Also we provide an upper bound forγvctof a connected cubic graph of ordern≥8. Then we try to provide a more stronger relationship betweenγandγvct.

APA, Harvard, Vancouver, ISO, and other styles

7

Voorhees, Burton, and Bergerud Ryder. "Simple graph models of information spread in finite populations." Royal Society Open Science 2, no. 5 (May 2015): 150028. http://dx.doi.org/10.1098/rsos.150028.

Full text

Abstract:

We consider several classes of simple graphs as potential models for information diffusion in a structured population. These include biases cycles, dual circular flows, partial bipartite graphs and what we call ‘single-link’ graphs. In addition to fixation probabilities, we study structure parameters for these graphs, including eigenvalues of the Laplacian, conductances, communicability and expected hitting times. In several cases, values of these parameters are related, most strongly so for partial bipartite graphs. A measure of directional bias in cycles and circular flows arises from the non-zero eigenvalues of the antisymmetric part of the Laplacian and another measure is found for cycles as the value of the transition probability for which hitting times going in either direction of the cycle are equal. A generalization of circular flow graphs is used to illustrate the possibility of tuning edge weights to match pre-specified values for graph parameters; in particular, we show that generalizations of circular flows can be tuned to have fixation probabilities equal to the Moran probability for a complete graph by tuning vertex temperature profiles. Finally, single-link graphs are introduced as an example of a graph involving a bottleneck in the connection between two components and these are compared to the partial bipartite graphs.

APA, Harvard, Vancouver, ISO, and other styles

8

TROTTA, BELINDA. "RESIDUAL PROPERTIES OF SIMPLE GRAPHS." Bulletin of the Australian Mathematical Society 82, no. 3 (August 18, 2010): 488–504. http://dx.doi.org/10.1017/s0004972710000420.

Full text

Abstract:

AbstractClark et al. [‘The axiomatizability of topological prevarieties’, Adv. Math.218 (2008), 1604–1653] have shown that, for k≥2, there exists a Boolean topological graph that is k-colourable but not topologically k-colourable; that is, for every ϵ>0, it cannot be coloured by a paintbrush of width ϵ. We generalize this result to show that, for k≥2, there is a Boolean topological graph that is 2-colourable but not topologically k-colourable. This graph is an inverse limit of finite graphs which are shown to exist by an Erdős-style probabilistic argument of Hell and Nešetřil [‘The core of a graph’, Discrete Math.109 (1992), 117–126]. We use the fact that there exists a Boolean topological graph that is 2-colourable but not k-colourable, and some other results (some new and some previously known), to answer the question of which finitely generated topological residual classes of graphs are axiomatizable by universal Horn sentences. A more general version of this question was raised in the above-mentioned paper by Clark et al., and has been investigated by various authors for other structures.

APA, Harvard, Vancouver, ISO, and other styles

9

Devriendt, Karel, and Piet Van Mieghem. "The simplex geometry of graphs." Journal of Complex Networks 7, no. 4 (January 29, 2019): 469–90. http://dx.doi.org/10.1093/comnet/cny036.

Full text

Abstract:

AbstractGraphs are a central object of study in various scientific fields, such as discrete mathematics, theoretical computer science and network science. These graphs are typically studied using combinatorial, algebraic or probabilistic methods, each of which highlights the properties of graphs in a unique way. Here, we discuss a novel approach to study graphs: the simplex geometry (a simplex is a generalized triangle). This perspective, proposed by Miroslav Fiedler, introduces techniques from (simplex) geometry into the field of graph theory and conversely, via an exact correspondence. We introduce this graph-simplex correspondence, identify a number of basic connections between graph characteristics and simplex properties, and suggest some applications as example.

APA, Harvard, Vancouver, ISO, and other styles

10

BAHR, PATRICK. "Convergence in infinitary term graph rewriting systems is simple." Mathematical Structures in Computer Science 28, no. 8 (August 9, 2018): 1363–414. http://dx.doi.org/10.1017/s0960129518000166.

Full text

Abstract:

Term graph rewriting provides a formalism for implementing term rewriting in an efficient manner by emulating duplication via sharing. Infinitary term rewriting has been introduced to study infinite term reduction sequences. Such infinite reductions can be used to model non-strict evaluation. In this paper, we unify term graph rewriting and infinitary term rewriting thereby addressing both components of lazy evaluation: non-strictness and sharing. In contrast to previous attempts to formalise infinitary term graph rewriting, our approach is based on a simple and natural generalisation of the modes of convergence of infinitary term rewriting. We show that this new approach is better suited for infinitary term graph rewriting as it is simpler and more general. The latter is demonstrated by the fact that our notions of convergence give rise to two independent canonical and exhaustive constructions of infinite term graphs from finite term graphs via metric and ideal completion. In addition, we show that our notions of convergence on term graphs are sound w.r.t. the ones employed in infinitary term rewriting in the sense that convergence is preserved by unravelling term graphs to terms. Moreover, the resulting infinitary term graph calculi provide a unified framework for both infinitary term rewriting and term graph rewriting, which makes it possible to study the correspondences between these two worlds more closely.

APA, Harvard, Vancouver, ISO, and other styles

11

Abughazalah, Nabilah, Naveed Yaqoob, and Asif Bashir. "Cayley Graphs over LA-Groups and LA-Polygroups." Mathematical Problems in Engineering 2021 (May 10, 2021): 1–9. http://dx.doi.org/10.1155/2021/4226232.

Full text

Abstract:

The purpose of this paper is the study of simple graphs that are generalized Cayley graphs over LA-polygroups GCLAP − graphs . In this regard, we construct two new extensions for building LA-polygroups. Then, we define Cayley graph over LA-group and GCLAP-graph. Further, we investigate a few properties of them to show that each simple graph of order three, four, and five (except cycle graph of order five which may or may not be a GCLAP-graph) is a GCLAP-graph and then we prove this result.

APA, Harvard, Vancouver, ISO, and other styles

12

SKULRATTANAKULCHAI, SAN, and HAROLD N. GABOW. "COLORING ALGORITHMS ON SUBCUBIC GRAPHS." International Journal of Foundations of Computer Science 15, no. 01 (February 2004): 21–40. http://dx.doi.org/10.1142/s0129054104002285.

Full text

Abstract:

We present efficient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The first algorithm is for 4-edge coloring, or more generally, 4-list-edge coloring. Our algorithm runs in linear time, and appears to be simpler than previous ones. The second algorithm is the first randomized EREW PRAM algorithm for the same problem. It uses O(n/ log n) processors and runs in O( log n) time with high probability, where n is the number of vertices of the graph. The third algorithm is the first linear-time algorithm to 5-total-color subcubic graphs. The fourth algorithm generalizes this to get the first linear-time algorithm to 5-list-total-color subcubic graphs. Our sequential algorithms are based on a method of ordering the vertices and edges by traversing a spanning tree of a graph in a bottom-up fashion. Our parallel algorithm is based on a simple decomposition principle for subcubic graphs.

APA, Harvard, Vancouver, ISO, and other styles

13

Wu, Tongsuo, and Li Chen. "Simple Graphs and Zero-divisor Semigroups." Algebra Colloquium 16, no. 02 (June 2009): 211–18. http://dx.doi.org/10.1142/s1005386709000212.

Full text

Abstract:

In this paper, we provide examples of graphs which uniquely determine a zero-divisor semigroup. We show two classes of graphs that have no corresponding semigroups. Especially, we prove that no complete r-partite graph together with two or more end vertices (each linked to distinct vertices) has corresponding semigroups.

APA, Harvard, Vancouver, ISO, and other styles

14

Amanto, Amanto, Notiragayu Notiragayu, La Zakaria, and Wamiliana Wamiliana. "The relationship of the formulas for the number of connected vertices labeled graphs with order five and order six without loops." Desimal: Jurnal Matematika 4, no. 3 (November 30, 2021): 357–64. http://dx.doi.org/10.24042/djm.v4i3.10006.

Full text

Abstract:

Given a graph with n points and m lines. If each vertex is labeled, then it can be constructed many graphs, connected, or disconnected graphs. A graph G is called a connected graph if there is at least one path that connects a pair of vertices in G. In addition, the graph formed may be simple or not simple. A simple graph is a graph that does not contain loops or parallel lines. A loop is a line that connects a point to itself, and a parallel line is two or more lines that connect the same pair of points. This paper will discuss the relationship between the formula patterns for calculating the number of connected graphs labeled with vertices of order five and six without loops.

APA, Harvard, Vancouver, ISO, and other styles

15

Yang, Xiaocheng, Mingyu Yan, Shirui Pan, Xiaochun Ye, and Dongrui Fan. "Simple and Efficient Heterogeneous Graph Neural Network." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 9 (June 26, 2023): 10816–24. http://dx.doi.org/10.1609/aaai.v37i9.26283.

Full text

Abstract:

Heterogeneous graph neural networks (HGNNs) have the powerful capability to embed rich structural and semantic information of a heterogeneous graph into node representations. Existing HGNNs inherit many mechanisms from graph neural networks (GNNs) designed for homogeneous graphs, especially the attention mechanism and the multi-layer structure. These mechanisms bring excessive complexity, but seldom work studies whether they are really effective on heterogeneous graphs. In this paper, we conduct an in-depth and detailed study of these mechanisms and propose the Simple and Efficient Heterogeneous Graph Neural Network (SeHGNN). To easily capture structural information, SeHGNN pre-computes the neighbor aggregation using a light-weight mean aggregator, which reduces complexity by removing overused neighbor attention and avoiding repeated neighbor aggregation in every training epoch. To better utilize semantic information, SeHGNN adopts the single-layer structure with long metapaths to extend the receptive field, as well as a transformer-based semantic fusion module to fuse features from different metapaths. As a result, SeHGNN exhibits the characteristics of a simple network structure, high prediction accuracy, and fast training speed. Extensive experiments on five real-world heterogeneous graphs demonstrate the superiority of SeHGNN over the state-of-the-arts on both accuracy and training speed.

APA, Harvard, Vancouver, ISO, and other styles

16

Hart, James, and Brian Frazier. "Finite Simple Graphs and Their Associated Graph Lattices." Theory and Applications of Graphs 5, no. 2 (2018): 1–20. http://dx.doi.org/10.20429/tag.2018.050206.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Türkmen, Burcu Nişancı, and Gülçin Karaca. "Finitely Generated Simple Graphs." International Journal of Applied Sciences and Smart Technologies 5, no. 2 (December 26, 2023): 191–200. http://dx.doi.org/10.24071/ijasst.v5i2.6739.

Full text

Abstract:

In this paper, Kirchhoff, Hyper-Wiener, Randic, Szeged, Pi index calculations of finitely generated (cyclic) simple graphs on the samples were made and classification of some finitely generated (cyclic) groups was achieved with the help of graph theory.

APA, Harvard, Vancouver, ISO, and other styles

18

KHEIRABADI, M., and A. R. MOGHADDAMFAR. "RECOGNIZING SOME FINITE SIMPLE GROUPS BY NONCOMMUTING GRAPH." Journal of Algebra and Its Applications 11, no. 04 (July 31, 2012): 1250077. http://dx.doi.org/10.1142/s0219498812500776.

Full text

Abstract:

Let G be a nonabelian group. We define the noncommuting graph ∇(G) of G as follows: its vertex set is G\Z(G), the noncentral elements of G, and two distinct vertices x and y of ∇(G) are joined by an edge if and only if x and y do not commute as elements of G, i.e. [x, y] ≠ 1. The finite group L is said to be recognizable by noncommuting graph if, for every finite group G, ∇(G) ≅ ∇ (L) implies G ≅ L. In the present article, it is shown that the noncommuting graph of a group with trivial center can determine its prime graph. From this, the following theorem is derived. If two finite groups with trivial centers have isomorphic noncommuting graphs, then their prime graphs coincide. It is also proved that the projective special unitary groups U4(4), U4(8), U4(9), U4(11), U4(13), U4(16), U4(17) and the projective special linear groups L9(2), L16(2) are recognizable by noncommuting graph.

APA, Harvard, Vancouver, ISO, and other styles

19

ALT, HELMUT, ULRICH FUCHS, and KLAUS KRIEGEL. "On the Number of Simple Cycles in Planar Graphs." Combinatorics, Probability and Computing 8, no. 5 (September 1999): 397–405. http://dx.doi.org/10.1017/s0963548399003995.

Full text

Abstract:

Let C(G) denote the number of simple cycles of a graph G and let C(n) be the maximum of C(G) over all planar graphs with n nodes. We present a lower bound on C(n), constructing graphs with at least 2.28n cycles. Applying some probabilistic arguments we prove an upper bound of 3.37n.We also discuss this question restricted to the subclasses of grid graphs, bipartite graphs, and 3-colourable triangulated graphs.

APA, Harvard, Vancouver, ISO, and other styles

20

FÜRER, MARTIN, and SHIVA PRASAD KASIVISWANATHAN. "Approximately Counting Embeddings into Random Graphs." Combinatorics, Probability and Computing 23, no. 6 (July 9, 2014): 1028–56. http://dx.doi.org/10.1017/s0963548314000339.

Full text

Abstract:

LetHbe a graph, and letCH(G) be the number of (subgraph isomorphic) copies ofHcontained in a graphG. We investigate the fundamental problem of estimatingCH(G). Previous results cover only a few specific instances of this general problem, for example the case whenHhas degree at most one (the monomer-dimer problem). In this paper we present the first general subcase of the subgraph isomorphism counting problem, which is almost always efficiently approximable. The results rely on a new graph decomposition technique. Informally, the decomposition is a labelling of the vertices such that every edge is between vertices with different labels, and for every vertex all neighbours with a higher label have identical labels. The labelling implicitly generates a sequence of bipartite graphs, which permits us to break the problem of counting embeddings of large subgraphs into that of counting embeddings of small subgraphs. Using this method, we present a simple randomized algorithm for the counting problem. For all decomposable graphsHand all graphsG, the algorithm is an unbiased estimator. Furthermore, for all graphsHhaving a decomposition where each of the bipartite graphs generated is small and almost all graphsG, the algorithm is a fully polynomial randomized approximation scheme.We show that the graph classes ofHfor which we obtain a fully polynomial randomized approximation scheme for almost allGincludes graphs of degree at most two, bounded-degree forests, bounded-width grid graphs, subdivision of bounded-degree graphs, and major subclasses of outerplanar graphs, series-parallel graphs and planar graphs of large girth, whereas unbounded-width grid graphs are excluded. Moreover, our general technique can easily be applied to proving many more similar results.

APA, Harvard, Vancouver, ISO, and other styles

21

Nieva, Alex Ralph, and Karen P. Nocum. "On Some Properties of Non-traceable Cubic Bridge Graph." European Journal of Pure and Applied Mathematics 15, no. 4 (October 31, 2022): 1536–48. http://dx.doi.org/10.29020/nybg.ejpam.v15i4.4453.

Full text

Abstract:

Graphs considered in this paper are simple finite undirected graphs without loops or multiple edges. A simple graphs where each vertex has degree 3 is called cubic graphs. A cubic graphs, that is, 1-connected or cubic bridge graph is traceable if its contains Hamiltonian path otherwise, non-traceable. In this paper, we introduce a new family of cubic graphs called Non-Traceable Cubic Bridge Graph (NTCBG) that satisfy the conjecture of Zoeram and Yaqubi (2017). In addition, we defined two important connected component of NTCBG that is, central fragment that give assurance for a graph to be non-traceable and its branches. Some properties of NTCBG such as chromatic number and clique number were also provided.

APA, Harvard, Vancouver, ISO, and other styles

22

BURNESS, TIMOTHY C., and ELISA COVATO. "ON THE PRIME GRAPH OF SIMPLE GROUPS." Bulletin of the Australian Mathematical Society 91, no. 2 (October 8, 2014): 227–40. http://dx.doi.org/10.1017/s0004972714000707.

Full text

Abstract:

AbstractLet $G$ be a finite group, let ${\it\pi}(G)$ be the set of prime divisors of $|G|$ and let ${\rm\Gamma}(G)$ be the prime graph of $G$. This graph has vertex set ${\it\pi}(G)$, and two vertices $r$ and $s$ are adjacent if and only if $G$ contains an element of order $rs$. Many properties of these graphs have been studied in recent years, with a particular focus on the prime graphs of finite simple groups. In this note, we determine the pairs $(G,H)$, where $G$ is simple and $H$ is a proper subgroup of $G$ such that ${\rm\Gamma}(G)={\rm\Gamma}(H)$.

APA, Harvard, Vancouver, ISO, and other styles

23

Dutta, Supriyo, Bibhas Adhikari, and Subhashish Banerjee. "Condition for zero and nonzero discord in graph Laplacian quantum states." International Journal of Quantum Information 17, no. 02 (March 2019): 1950018. http://dx.doi.org/10.1142/s0219749919500187.

Full text

Abstract:

This work is at the interface of graph theory and quantum mechanics. Quantum correlations epitomize the usefulness of quantum mechanics. Quantum discord is an interesting facet of bipartite quantum correlations. Earlier, it was shown that every combinatorial graph corresponds to quantum states whose characteristics are reflected in the structure of the underlined graph. A number of combinatorial relations between quantum discord and simple graphs were studied. To extend the scope of these studies, we need to generalize the earlier concepts applicable to simple graphs to weighted graphs, corresponding to a diverse class of quantum states. To this effect, we determine the class of quantum states whose density matrix representation can be derived from graph Laplacian matrices associated with a weighted directed graph and call them graph Laplacian quantum states. We find the graph theoretic conditions for zero and nonzero quantum discord for these states. We apply these results on some important pure two qubit states, as well as a number of mixed quantum states, such as the Werner, Isotropic, and [Formula: see text]-states. We also consider graph Laplacian states corresponding to simple graphs as a special case.

APA, Harvard, Vancouver, ISO, and other styles

24

Cui, Yan, and Chao Dong Cui. "Study on Necessary and Sufficient Conditions for Euler Graph and Hamilton Graph." Advanced Materials Research 1044-1045 (October 2014): 1357–61. http://dx.doi.org/10.4028/www.scientific.net/amr.1044-1045.1357.

Full text

Abstract:

Three theorems are proposed in this paper. The first theorem is that a connected undirected graph G is an Euler graph if and only if G can be expressed as the union of two circles without overlapped sides. Namely, equation satisfies. The second theorem is that a connected simple undirected graph is a Hamilton graph if and only if G contains a sub-graph generated by union of circles of sub-graphs derived from two endpoints of common side. Namely, the equation satisfies (meaning of symbols in the equations see main body of this paper). The third theorem is that a connected simple undirected graph is a Hamilton graph if and only if the loop sum of two circles, and, of sub-graphs derived from two endpoints of common side in graph G is a sub-graphs of loop graph Cn.

APA, Harvard, Vancouver, ISO, and other styles

25

Khuluq, Muhammad Husnul, Vira Hari Krisnawati, and Noor Hidayat. "On Group-Vertex-Magic Labeling of Simple Graphs." CAUCHY: Jurnal Matematika Murni dan Aplikasi 8, no. 2 (November 15, 2023): 167–74. http://dx.doi.org/10.18860/ca.v8i2.23621.

Full text

Abstract:

Let A be an Abelian group with identity 0. The A-vertex-magic labeling of a graph G is a mapping from the set of vertices in G to A-{0} such that the sum of the labels of every open neighborhood vertex of v is equal, for every vertex v in G. In this article, we discuss group-vertex-magic labeling of some simple graphs by using the Abelian group Zk, with natural numbers k1. We investigated some classes of simple graphs are path graphs, complete graphs, cyclic graphs, and star graphs. The method we used in this article is literature study and then developing the properties of vertex-magic labeling of some simple graphs, that are path graphs, complete graphs, cyclic graphs, and star graphs. We obtain that complete graphs, cyclic graphs, and star graphs have Zk-vertex-magic labeling, while path graphs have vertex-magic labeling only for n=2,3.

APA, Harvard, Vancouver, ISO, and other styles

26

DIAO, Y., G. HETYEI, and K. HINSON. "TUTTE POLYNOMIALS OF TENSOR PRODUCTS OF SIGNED GRAPHS AND THEIR APPLICATIONS IN KNOT THEORY." Journal of Knot Theory and Its Ramifications 18, no. 05 (May 2009): 561–89. http://dx.doi.org/10.1142/s0218216509007075.

Full text

Abstract:

It is well-known that the Jones polynomial of an alternating knot is closely related to the Tutte polynomial of a special graph obtained from a regular projection of the knot. Relying on the results of Bollobás and Riordan, we introduce a generalization of Kauffman's Tutte polynomial of signed graphs for which describing the effect of taking a signed tensor product of signed graphs is very simple. We show that this Tutte polynomial of a signed tensor product of signed graphs may be expressed in terms of the Tutte polynomials of the original signed graphs by using a simple substitution rule. Our result enables us to compute the Jones polynomials of some large non-alternating knots. The combinatorics used to prove our main result is similar to Tutte's original way of counting "activities" and specializes to a new, perhaps simpler proof of the known formulas for the ordinary Tutte polynomial of the tensor product of unsigned graphs or matroids.

APA, Harvard, Vancouver, ISO, and other styles

27

Lin, Jephian Chin-Hung. "Odd Cycle Zero Forcing Parameters and the Minimum Rank of Graph Blowups." Electronic Journal of Linear Algebra 31 (February 5, 2016): 42–59. http://dx.doi.org/10.13001/1081-3810.2836.

Full text

Abstract:

The minimum rank problem for a simple graph G and a given field F is to determine the smallest possible rank among symmetric matrices over F whose i, j-entry, i â j, is nonzero whenever i is adjacent to j, and zero otherwise; the diagonal entries can be any element in F. In contrast, loop graphs \mathscr{G} go one step further to restrict the diagonal i, i-entries as nonzero whenever i has a loop, and zero otherwise. When char F â 2, the odd cycle zero forcing number and the enhanced odd cycle zero forcing number are introduced as bounds for loop graphs and simple graphs, respectively. A relation between loop graphs and simple graphs through graph blowups is developed, so that the minimum rank problem of some families of simple graphs can be reduced to that of much smaller loop graphs.

APA, Harvard, Vancouver, ISO, and other styles

28

Ouadid, Youssef, Abderrahmane Elbalaoui, Mehdi Boutaounte, Mohamed Fakir, and Brahim Minaoui. "Handwritten tifinagh character recognition using simple geometric shapes and graphs." Indonesian Journal of Electrical Engineering and Computer Science 13, no. 2 (February 1, 2019): 598. http://dx.doi.org/10.11591/ijeecs.v13.i2.pp598-605.

Full text

Abstract:

<p>In this paper, a graph based handwritten Tifinagh character recognition system is presented. In preprocessing Zhang Suen algorithm is enhanced. In features extraction, a novel key point extraction algorithm is presented. Images are then represented by adjacency matrices defining graphs where nodes represent feature points extracted by a novel algorithm. These graphs are classified using a graph matching method. Experimental results are obtained using two databases to test the effectiveness. The system shows good results in terms of recognition rate.</p>

APA, Harvard, Vancouver, ISO, and other styles

29

Seidy, Essam EI, Salah ElDin Hussein, and Atef Abo Elkher. "Spectra of some Operations on Graphs." JOURNAL OF ADVANCES IN MATHEMATICS 11, no. 9 (January 8, 2016): 5654–60. http://dx.doi.org/10.24297/jam.v11i9.828.

Full text

Abstract:

In this paper, we consider a finite undirected and connected simple graph G(E, V) with vertex set V(G) and edge set E(G).We introduced a new computes the spectra of some operations on simple graphs [union of disjoint graphs, join of graphs, cartesian product of graphs, strong cartesian product of graphs, direct product of graphs].

APA, Harvard, Vancouver, ISO, and other styles

30

Pardo-Guerra, Sebastian, Vivek Kurien George, Vikash Morar, Joshua Roldan, and Gabriel Alex Silva. "Extending Undirected Graph Techniques to Directed Graphs via Category Theory." Mathematics 12, no. 9 (April 29, 2024): 1357. http://dx.doi.org/10.3390/math12091357.

Full text

Abstract:

We use Category Theory to construct a ‘bridge’ relating directed graphs with undirected graphs, such that the notion of direction is preserved. Specifically, we provide an isomorphism between the category of simple directed graphs and a category we call ‘prime graphs category’; this has as objects labeled undirected bipartite graphs (which we call prime graphs), and as morphisms undirected graph morphisms that preserve the labeling (which we call prime graph morphisms). This theoretical bridge allows us to extend undirected graph techniques to directed graphs by converting the directed graphs into prime graphs. To give a proof of concept, we show that our construction preserves topological features when applied to the problems of network alignment and spectral graph clustering.

APA, Harvard, Vancouver, ISO, and other styles

31

Jiao, Qingju, Han Zhang, Jingwen Wu, Nan Wang, Guoying Liu, and Yongge Liu. "A simple and effective convolutional operator for node classification without features by graph convolutional networks." PLOS ONE 19, no. 4 (April 30, 2024): e0301476. http://dx.doi.org/10.1371/journal.pone.0301476.

Full text

Abstract:

Graph neural networks (GNNs), with their ability to incorporate node features into graph learning, have achieved impressive performance in many graph analysis tasks. However, current GNNs including the popular graph convolutional network (GCN) cannot obtain competitive results on the graphs without node features. In this work, we first introduce path-driven neighborhoods, and then define an extensional adjacency matrix as a convolutional operator. Second, we propose an approach named exopGCN which integrates the simple and effective convolutional operator into GCN to classify the nodes in the graphs without features. Experiments on six real-world graphs without node features indicate that exopGCN achieves better performance than other GNNs on node classification. Furthermore, by adding the simple convolutional operator into 13 GNNs, the accuracy of these methods are improved remarkably, which means that our research can offer a general skill to improve accuracy of GNNs. More importantly, we study the relationship between node classification by GCN without node features and community detection. Extensive experiments including six real-world graphs and nine synthetic graphs demonstrate that the positive relationship between them can provide a new direction on exploring the theories of GCNs.

APA, Harvard, Vancouver, ISO, and other styles

32

Yurttas Gunes, Aysun, Hacer Ozden Ayna, and Ismail Naci Cangul. "The Effect of Vertex and Edge Removal on Sombor Index." Symmetry 16, no. 2 (February 1, 2024): 170. http://dx.doi.org/10.3390/sym16020170.

Full text

Abstract:

A vertex degree based topological index called the Sombor index was recently defined in 2021 by Gutman and has been very popular amongst chemists and mathematicians. We determine the amount of change of the Sombor index when some elements are removed from a graph. This is done for several graph elements, including a vertex, an edge, a cut vertex, a pendant edge, a pendant path, and a bridge in a simple graph. Also, pendant and non-pendant cases are studied. Using the obtained formulae successively, one can find the Sombor index of a large graph by means of the Sombor indices of smaller graphs that are just graphs obtained after removal of some vertices or edges. Sometimes, using iteration, one can manage to obtain a property of a really large graph in terms of the same property of many other subgraphs. Here, the calculations are made for a pendant and non-pendant vertex, a pendant and non-pendant edge, a pendant path, a bridge, a bridge path from a simple graph, and, finally, for a loop and a multiple edge from a non-simple graph. Using these results, the Sombor index of cyclic graphs and tadpole graphs are obtained. Finally, some Nordhaus–Gaddum type results are obtained for the Sombor index.

APA, Harvard, Vancouver, ISO, and other styles

33

Deb, Swakshar, Sejuti Rahman, and Shafin Rahman. "SEA-GWNN: Simple and Effective Adaptive Graph Wavelet Neural Network." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 10 (March 24, 2024): 11740–48. http://dx.doi.org/10.1609/aaai.v38i10.29058.

Full text

Abstract:

The utilization of wavelet-based techniques in graph neural networks (GNNs) has gained considerable attention, particularly in the context of node classification. Although existing wavelet-based approaches have shown promise, they are constrained by their reliance on pre-defined wavelet filters, rendering them incapable of effectively adapting to signals that reside on graphs based on tasks at hand. Recent research endeavors address this issue through the introduction of a wavelet lifting transform. However, this technique necessitates the use of bipartite graphs, causing a transformation of the original graph structure into a bipartite configuration. This alteration of graph topology results in the generation of undesirable wavelet filters, thereby undermining the effectiveness of the method. In response to these challenges, we propose a novel simple and effective adaptive graph wavelet neural network (SEA-GWNN) class that employs the lifting scheme on arbitrary graph structures while upholding the original graph topology by leveraging multi-hop computation trees. A noteworthy aspect of the approach is the focus on local substructures represented as acyclic trees, wherein the lifting strategy is applied in a localized manner. This locally defined lifting scheme effectively combines high-pass and low-pass frequency information to enhance node representations. Furthermore, to reduce computing costs, we propose to decouple the higher- order lifting operators and induce them from the lower-order structures. Finally, we benchmark our model on several real- world datasets spanning four distinct categories, including citation networks, webpages, the film industry, and large-scale graphs and the experimental results showcase the efficacy of the proposed SEA-GWNN.

APA, Harvard, Vancouver, ISO, and other styles

34

Holme, Petter, and Mikael Huss. "Substance graphs are optimal simple-graph representations of metabolism." Chinese Science Bulletin 55, no. 27-28 (September 2010): 3161–68. http://dx.doi.org/10.1007/s11434-010-4086-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Solomko, Viktoriia, and Vladyslav Sobolev. "Constructing the Mate of Cospectral 5-regular Graphs with and without a Perfect Matching." Mohyla Mathematical Journal 4 (May 19, 2022): 24–27. http://dx.doi.org/10.18523/2617-70804202124-27.

Full text

Abstract:

The problem of finding a perfect matching in an arbitrary simple graph is well known and popular in graph theory. It is used in various fields, such as chemistry, combinatorics, game theory etc. The matching of M in a simple graph G is a set of pairwise nonadjacent edges, ie, those that do not have common vertices. Matching is called perfect if it covers all vertices of the graph, ie each of the vertices of the graph is incidental to exactly one of the edges. By Koenig's theorem, regular bipartite graphs of positive degree always have perfect matching. However, graphs that are not bipartite need further research. Another interesting problem of graph theory is the search for pairwise nonisomorphic cospectral graphs. In addition, it is interesting to find cospectral graphs that have additional properties. For example, finding cospectral graphs with and without a perfect matching. The fact that for each there is a pair of cospectral connected k-regular graphs with and without a perfect matching had been investigated by Blazsik, Cummings and Haemers. The pair of cospectral connected 5-regular graphs with and without a perfect matching is constructed by using Godsil-McKay switching in the paper.

APA, Harvard, Vancouver, ISO, and other styles

36

Alrowaili, Dalal Awadh, Uzma Ahmad, Saira Hameeed, and Muhammad Javaid. "Graphs with mixed metric dimension three and related algorithms." AIMS Mathematics 8, no. 7 (2023): 16708–23. http://dx.doi.org/10.3934/math.2023854.

Full text

Abstract:

<abstract><p>Let $ G = (V, E) $ be a simple connected graph. A vertex $ x\in V(G) $ resolves the elements $ u, v\in E(G)\cup V(G) $ if $ d_G(x, u)\neq d_G(x, v) $. A subset $ S\subseteq V(G) $ is a mixed metric resolving set for $ G $ if every two elements of $ G $ are resolved by some vertex of $ S $. A set of smallest cardinality of mixed metric generator for $ G $ is called the mixed metric dimension. In this paper trees and unicyclic graphs having mixed dimension three are classified. The main aim is to investigate the structure of a simple connected graph having mixed dimension three with respect to the order of graph, maximum degree of basis elements and distance partite sets of basis elements. In particular to find necessary and sufficient conditions for a graph to have mixed metric dimension 3. Moreover three separate algorithms are developed for trees, unicyclic graphs and in general for simple connected graph $ J_{n}\ncong P_{n} $ with $ n\geq 3 $ to determine "whether these graphs have mixed dimension three or not?". If these graphs have mixed dimension three, then these algorithms provide a mixed basis of an input graph.</p></abstract>

APA, Harvard, Vancouver, ISO, and other styles

37

Mathew, Suji Elizabeth, and Sunny Joseph Kalayathankal. "Some Results on Pendant Regular Graphs." Pan-American Journal of Mathematics 2 (November 13, 2023): 12. http://dx.doi.org/10.28919/cpr-pajm/2-12.

Full text

Abstract:

Let G = (V, E) be a simple connected graph with o(G) = n and s(G) = m. A graph with pendant vertices is called Pendant Graphs or simply P-Graphs. In this paper we define the regularity of Pendant Graphs w.r.t. the degrees of support vertex of each pendant vertices. Sufficient conditions for pendant graphs are discussed in this paper.

APA, Harvard, Vancouver, ISO, and other styles

38

Muhammad, Ibrahim, and Abubakar Umar. "Permutation graphs with co-inversion on Γ<sub>1</sub> - non-deranged permutations." Caliphate Journal of Science and Technology 5, no. 2 (August 8, 2023): 127–31. http://dx.doi.org/10.4314/cajost.v5i2.6.

Full text

Abstract:

In this paper, we define permutation graphs on Γ1 -non-deranged permutations using the set of co-inversion as edge set, and the values of permutation as the set of vertices. From the graphs, we observed that diameter and radius of the graph of any ω1 is one, the graph of any ωp-1 ∈ GΓ1p simple, the graph of ω1 is completed and other properties of the graphs were also observed.

APA, Harvard, Vancouver, ISO, and other styles

39

Journal, Baghdad Science. "Tadpole Domination in Graphs." Baghdad Science Journal 15, no. 4 (December 9, 2018): 466–71. http://dx.doi.org/10.21123/bsj.15.4.466-471.

Full text

Abstract:

A new type of the connected domination parameters called tadpole domination number of a graph is introduced. Tadpole domination number for some standard graphs is determined, and some bounds for this number are obtained. Additionally, a new graph, finite, simple, undirected and connected, is introduced named weaver graph. Tadpole domination is calculated for this graph with other families of graphs.

APA, Harvard, Vancouver, ISO, and other styles

40

Kazi, Sabeena, and Harishchandra Ramane. "Construction And Spectra Of Non-Regular Minimal Graphs." Journal of Engineering and Applied Sciences 9, no. 1 (2022): 30. http://dx.doi.org/10.5455/jeas.2022050103.

Full text

Abstract:

The number of distinct eigenvalues of the adjacency matrix of graph G is bounded below by d(G)+1, where d is the diameter of the graph. Graphs attaining this lower bound are known as minimal graphs. The spectrum of graph G, where G is a simple and undirected graph is the collection of different eigenvalues of the adjacency matrix with their multiplicities. This paper deals with the construction of non-regular minimal graphs, together with the study of their characteristic polynomial and spectra.

APA, Harvard, Vancouver, ISO, and other styles

41

Su, Huadong, and Yangjiang Wei. "Semipotent Rings Whose Unit Graphs Are Planar." Algebra Colloquium 27, no. 02 (May 7, 2020): 311–18. http://dx.doi.org/10.1142/s1005386720000255.

Full text

Abstract:

The unit graph of a ring is the simple graph whose vertices are the elements of the ring and where two distinct vertices are adjacent if and only if their sum is a unit of the ring. A simple graph is said to be planar if it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In this note, we completely characterize the semipotent rings whose unit graphs are planar. As a consequence, we list all semilocal rings with planar unit graphs.

APA, Harvard, Vancouver, ISO, and other styles

42

Ghorbani, Modjtaba, Matthias Dehmer, Shaghayegh Rahmani, and Mina Rajabi-Parsa. "A Survey on Symmetry Group of Polyhedral Graphs." Symmetry 12, no. 3 (March 2, 2020): 370. http://dx.doi.org/10.3390/sym12030370.

Full text

Abstract:

Every three-connected simple planar graph is a polyhedral graph and a cubic polyhedral graph with pentagonal and hexagonal faces is called as a classical fullerene. The aim of this paper is to survey some results about the symmetry group of cubic polyhedral graphs. We show that the order of symmetry group of such graphs divides 240.

APA, Harvard, Vancouver, ISO, and other styles

43

ERDŐS, PÉTER L., ISTVÁN MIKLÓS, and ZOLTÁN TOROCZKAI. "New Classes of Degree Sequences with Fast Mixing Swap Markov Chain Sampling." Combinatorics, Probability and Computing 27, no. 2 (November 2, 2017): 186–207. http://dx.doi.org/10.1017/s0963548317000499.

Full text

Abstract:

In network modelling of complex systems one is often required to sample random realizations of networks that obey a given set of constraints, usually in the form of graph measures. A much studied class of problems targets uniform sampling of simple graphs with given degree sequence or also with given degree correlations expressed in the form of a Joint Degree Matrix. One approach is to use Markov chains based on edge switches (swaps) that preserve the constraints, are irreducible (ergodic) and fast mixing. In 1999, Kannan, Tetali and Vempala (KTV) proposed a simple swap Markov chain for sampling graphs with given degree sequence, and conjectured that it mixes rapidly (in polynomial time) for arbitrary degree sequences. Although the conjecture is still open, it has been proved for special degree sequences, in particular for those of undirected and directed regular simple graphs, half-regular bipartite graphs, and graphs with certain bounded maximum degrees. Here we prove the fast mixing KTV conjecture for novel, exponentially large classes of irregular degree sequences. Our method is based on a canonical decomposition of degree sequences into split graph degree sequences, a structural theorem for the space of graph realizations and on a factorization theorem for Markov chains. After introducing bipartite ‘splitted’ degree sequences, we also generalize the canonical split graph decomposition for bipartite and directed graphs.

APA, Harvard, Vancouver, ISO, and other styles

44

Thalavayalil, Timmy Tomy, and Sudev Naduvath. "A study on coarse deg-centric graphs." Gulf Journal of Mathematics 16, no. 2 (April 12, 2024): 171–82. http://dx.doi.org/10.56947/gjom.v16i2.1877.

Full text

Abstract:

The coarse deg-centric graph of a simple, connected graph G, denoted by Gcd, is a graph constructed from G such that V(Gcd) = V(G) and E(Gcd) = {vi vj : dG( vi, vj) > degG(vi)}. This paper introduces and discusses the concepts of coarse deg-centric graphs and iterated coarse deg-centrication of a graph. It also presents the properties and structural characteristics of coarse deg-centric graphs of some graph families.

APA, Harvard, Vancouver, ISO, and other styles

45

Fran, Fransiskus, Nilamsari Kusumastuti, and Robiandi. "BILANGAN KROMATIK HARMONIS PADA GRAF PAYUNG, GRAF PARASUT, DAN GRAF SEMI PARASUT." Jurnal Matematika Sains dan Teknologi 24, no. 1 (May 20, 2023): 15–22. http://dx.doi.org/10.33830/jmst.v24i1.3945.2023.

Full text

Abstract:

This article discusses the harmonic coloring of simple graphs G, namely umbrella graphs, parachute graphs, and semi-parachute graphs. A vertex coloring on a graph G is a harmonic coloring if each pair of colors (based on edges or pair of vertices) appears at most once. The chromatic number associated with the harmonic coloring of graph G is called the harmonic chromatic number denoted XH(G). In this article, the exact values of harmonic chromatic numbers are obtained for umbrella graphs, parachute graphs, and semi-parachute graphs.

APA, Harvard, Vancouver, ISO, and other styles

46

Iranmanesh, Mohammad, and Mahboubeh Saheli. "Toward a Laplacian spectral determination of signed ∞-graphs." Filomat 32, no. 6 (2018): 2283–94. http://dx.doi.org/10.2298/fil1806283i.

Full text

Abstract:

A signed graph consists of a (simple) graph G=(V,E) together with a function ? : E ? {+,-} called signature. Matrices can be associated to signed graphs and the question whether a signed graph is determined by the set of its eigenvalues has gathered the attention of several researchers. In this paper we study the spectral determination with respect to the Laplacian spectrum of signed ?-graphs. After computing some spectral invariants and obtain some constraints on the cospectral mates, we obtain some non isomorphic signed graphs cospectral to signed ?-graphs and we study the spectral characterization of the signed ?-graphs containing a triangle.

APA, Harvard, Vancouver, ISO, and other styles

47

Akar H. Karim, Nabeel E. Arif, and Ayad M. Ramadan. "The M-Polynomial and Nirmala index of Certain Composite Graphs." Tikrit Journal of Pure Science 27, no. 3 (November 29, 2022): 92–101. http://dx.doi.org/10.25130/tjps.v27i3.45.

Full text

Abstract:

The M-Polynomial and Nirmala index are considered as two of the most recent found and important subjects in chemical graph theory. In this paper we drive and prove the computing formula of Nirmala index from the M-Polynomial, then compute the M-Polynomial for some certain composite graphs, and the Nirmala index via the computed M-Polynomial. The composite graphs are new defined graphs Kn(Pt)Km , Cn(e)Kn , and others obtained from simple graphs by certain graph operations such as join, corona, and cluster of any graph with some special graphs such as complete, path, …etc

APA, Harvard, Vancouver, ISO, and other styles

48

Farzaneh, Amirmohammad, Justin P. Coon, and Mihai-Alin Badiu. "Kolmogorov Basic Graphs and Their Application in Network Complexity Analysis." Entropy 23, no. 12 (November 29, 2021): 1604. http://dx.doi.org/10.3390/e23121604.

Full text

Abstract:

Throughout the years, measuring the complexity of networks and graphs has been of great interest to scientists. The Kolmogorov complexity is known as one of the most important tools to measure the complexity of an object. We formalized a method to calculate an upper bound for the Kolmogorov complexity of graphs and networks. Firstly, the most simple graphs possible, those with O(1) Kolmogorov complexity, were identified. These graphs were then used to develop a method to estimate the complexity of a given graph. The proposed method utilizes the simple structures within a graph to capture its non-randomness. This method is able to capture features that make a network closer to the more non-random end of the spectrum. The resulting algorithm takes a graph as an input and outputs an upper bound to its Kolmogorov complexity. This could be applicable in, for example evaluating the performances of graph compression methods.

APA, Harvard, Vancouver, ISO, and other styles

49

Imran, Muhammad, Murat Cancan, Muhammad Faisal Nadeem, and Yasir Ali. "Further results on edge irregularity strength of some graphs." Proyecciones (Antofagasta) 43, no. 1 (March 11, 2024): 133–51. http://dx.doi.org/10.22199/issn.0717-6279-6175.

Full text

Abstract:

The focal point of this paper is to precisely ascertain the edge irregularity strength of various finite, simple, and undirected captivating graphs, including splitting graph, shadow graph, jewel graph, jellyfish graph, and $m$ copies of 4-pan graph.

APA, Harvard, Vancouver, ISO, and other styles

50

Dai, Zemiao, Muhammad Naeem, Zainab Shafaqat, Manzoor Ahmad Zahid, and Shahid Qaisar. "On the P3-Coloring of Bipartite Graphs." Mathematics 11, no. 16 (August 12, 2023): 3487. http://dx.doi.org/10.3390/math11163487.

Full text

Abstract:

The advancement in coloring schemes of graphs is expanding over time to solve emerging problems. Recently, a new form of coloring, namely P3-coloring, was introduced. A simple graph is called a P3-colorable graph if its vertices can be colored so that all the vertices in each P3 path of the graph have different colors; this is called the P3-coloring of the graph. The minimum number of colors required to form a P3-coloring of a graph is called the P3-chromatic number of the graph. The aim of this article is to determine the P3-chromatic number of different well-known classes of bipartite graphs such as complete bipartite graphs, tree graphs, grid graphs, and some special types of bipartite graphs. Moreover, we have also presented some algorithms to produce a P3-coloring of these classes with a minimum number of colors required.

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!