Log in

Relevant bibliographies by topics / Simple graph / Journal articles

To see the other types of publications on this topic, follow the link: Simple graph.

Journal articles on the topic 'Simple graph'

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 'Simple graph.'

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

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

2

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

3

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

4

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

5

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

6

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

7

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

8

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

9

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

10

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

11

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

12

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

13

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

14

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

15

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

16

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

17

Van Mieghem, Piet. "PATHS IN THE SIMPLE RANDOM GRAPH AND THE WAXMAN GRAPH." Probability in the Engineering and Informational Sciences 15, no. 4 (October 2001): 535–55. http://dx.doi.org/10.1017/s0269964801154070.

Full text

Abstract:

The Waxman graphs are frequently chosen in simulations as topologies resembling communications networks. For the Waxman graphs, we present analytic, exact expressions for the link density (average number of links) and the average number of paths between two nodes. These results show the similarity of Waxman graphs to the simpler class G>p(N). The first result enables one to compare simulations performed on the Waxman graph with those on other graphs with same link density. The average number of paths in Waxman graphs can be useful to dimension (or estimate) routing paths in networks. Although higher-order moments of the number of paths in Gp(N) are difficult to compute analytically, the probability distribution of the hopcount of a path between two arbitrary nodes seems well approximated by a Poisson law.

APA, Harvard, Vancouver, ISO, and other styles

18

Guo, Hongyu, and Yongyi Mao. "Interpolating Graph Pair to Regularize Graph Classification." Proceedings of the AAAI Conference on Artificial Intelligence 37, no. 6 (June 26, 2023): 7766–74. http://dx.doi.org/10.1609/aaai.v37i6.25941.

Full text

Abstract:

We present a simple and yet effective interpolation-based regularization technique, aiming to improve the generalization of Graph Neural Networks (GNNs) on supervised graph classification. We leverage Mixup, an effective regularizer for vision, where random sample pairs and their labels are interpolated to create synthetic images for training. Unlike images with grid-like coordinates, graphs have arbitrary structure and topology, which can be very sensitive to any modification that alters the graph's semantic meanings. This posts two unanswered questions for Mixup-like regularization schemes: Can we directly mix up a pair of graph inputs? If so, how well does such mixing strategy regularize the learning of GNNs? To answer these two questions, we propose ifMixup, which first adds dummy nodes to make two graphs have the same input size and then simultaneously performs linear interpolation between the aligned node feature vectors and the aligned edge representations of the two graphs. We empirically show that such simple mixing schema can effectively regularize the classification learning, resulting in superior predictive accuracy to popular graph augmentation and GNN methods.

APA, Harvard, Vancouver, ISO, and other styles

19

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

20

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

21

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

22

Koch, Sebastian. "Underlying Simple Graphs." Formalized Mathematics 27, no. 3 (October 1, 2019): 237–59. http://dx.doi.org/10.2478/forma-2019-0023.

Full text

Abstract:

Summary In this article the notion of the underlying simple graph of a graph (as defined in [8]) is formalized in the Mizar system [5], along with some convenient variants. The property of a graph to be without decorators (as introduced in [7]) is formalized as well to serve as the base of graph enumerations in the future.

APA, Harvard, Vancouver, ISO, and other styles

23

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

24

Galán, Severino F. "Simple decentralized graph coloring." Computational Optimization and Applications 66, no. 1 (July 25, 2016): 163–85. http://dx.doi.org/10.1007/s10589-016-9862-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

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

26

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

27

WAN, PENG-JUN, KHALED M. ALZOUBI, and OPHIR FRIEDER. "A SIMPLE HEURISTIC FOR MINIMUM CONNECTED DOMINATING SET IN GRAPHS." International Journal of Foundations of Computer Science 14, no. 02 (April 2003): 323–33. http://dx.doi.org/10.1142/s0129054103001753.

Full text

Abstract:

Let α2(G), γ(G) and γc(G) be the 2-independence number, the domination number, and the connected domination number of a graph G respectively. Then α2(G) ≤ γ (G) ≤ γc(G). In this paper , we present a simple heuristic for Minimum Connected Dominating Set in graphs. When running on a graph G excluding Km (the complete graph of order m) as a minor, the heuristic produces a connected dominating set of cardinality at most 7α2(G) - 4 if m = 3, or at most [Formula: see text] if m ≥ 4. In particular, if running on a planar graph G, the heuristic outputs a connected dominating set of cardinality at most 15α2(G) - 5.

APA, Harvard, Vancouver, ISO, and other styles

28

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

29

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

30

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

31

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

32

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

33

Montenegro, Eduardo, Eduardo Cabrera, José González Campos, and Ronald Manríquez Peñafiel. "Linear representation of a graph." Boletim da Sociedade Paranaense de Matemática 37, no. 4 (January 9, 2018): 97–102. http://dx.doi.org/10.5269/bspm.v37i4.32949.

Full text

Abstract:

In this paper the linear representation of a graph is defined. A linear representation of a graph is a subgroup of $GL(p,\mathbb{R})$, the group of invertible matrices of order $ p $ and real coefficients. It will be demonstrated that every graph admits a linear representation. In this paper, simple and finite graphs will be used, framed in the graphs theory's area

APA, Harvard, Vancouver, ISO, and other styles

34

Beaufays, Françoise, and Eric A. Wan. "Relating Real-Time Backpropagation and Backpropagation-Through-Time: An Application of Flow Graph Interreciprocity." Neural Computation 6, no. 2 (March 1994): 296–306. http://dx.doi.org/10.1162/neco.1994.6.2.296.

Full text

Abstract:

We show that signal flow graph theory provides a simple way to relate two popular algorithms used for adapting dynamic neural networks, real-time backpropagation and backpropagation-through-time. Starting with the flow graph for real-time backpropagation, we use a simple transposition to produce a second graph. The new graph is shown to be interreciprocal with the original and to correspond to the backpropagation-through-time algorithm. Interreciprocity provides a theoretical argument to verify that both flow graphs implement the same overall weight update.

APA, Harvard, Vancouver, ISO, and other styles

35

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

36

Wang, Weizhong, and Dong Yang. "Bounds for Incidence Energy of Some Graphs." Journal of Applied Mathematics 2013 (2013): 1–7. http://dx.doi.org/10.1155/2013/757542.

Full text

Abstract:

LetGbe a simple graph. The incidence energy (IEfor short) ofGis defined as the sum of the singular values of the incidence matrix. In this paper, a new upper bound forIEof graphs in terms of the maximum degree is given. Meanwhile, bounds forIEof the line graph of a semiregular graph and the paraline graph of a regular graph are obtained.

APA, Harvard, Vancouver, ISO, and other styles

37

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

38

V.R.Kulli. "General Fifth M-Zagreb Indices and Fifth M-Zagreb Polynomials of PAMAM Dendrimers." International Journal of Fuzzy Mathematical Archive 13, no. 01 (2017): 99–103. http://dx.doi.org/10.22457/ijfma.v13n1a10.

Full text

Abstract:

A molecular graph or a chemical graph is a simple graph related to the structure of a chemical compound. In this paper, we introduce the general fifth M-Zagreb indices and fifth M3-Zagreb index and their polynomials of a molecular graph. Also we compute the general fifth M-Zagreb indices and fifth M3-Zagreb index of PAMAM dendrimer graphs. Finally, we compute the fifth M3-Zagreb polynomial of PAMAM dendrimer graphs.

APA, Harvard, Vancouver, ISO, and other styles

39

Voorhees, Burton. "Birth–death fixation probabilities for structured populations." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 469, no. 2153 (May 8, 2013): 20120248. http://dx.doi.org/10.1098/rspa.2012.0248.

Full text

Abstract:

This paper presents an adaptation of the Moran birth–death model of evolutionary processes on graphs. The present model makes use of the full population state space consisting of 2 N binary-valued vectors, and a Markov process on this space with a transition matrix defined by the edge weight matrix for any given graph. While the general case involves solution of 2 N – 2 linear equations, symmetry considerations substantially reduce this for graphs with large automorphism groups, and a number of simple examples are considered. A parameter called graph determinacy is introduced, measuring the extent to which the fate of any randomly chosen population state is determined. Some simple graphs that suppress or enhance selection are analysed, and comparison of several examples to the Moran process on a complete graph indicates that in some cases a graph may enhance selection relative to a complete graph for only limited values of the fitness parameter.

APA, Harvard, Vancouver, ISO, and other styles

40

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

41

Hajisharifi, N., and S. Yassemi. "Vertex decomposable graph." Publications de l'Institut Math?matique (Belgrade) 99, no. 113 (2016): 203–9. http://dx.doi.org/10.2298/pim1613203h.

Full text

Abstract:

Let G be a simple graph on the vertex set V (G) and S = {x11,...,xn1} a subset of V (G). Let m1,...,mn ? 2 be integers and G1,...,Gn connected simple graphs on the vertex sets V (Gi) = {xi1,..., ximi} for i = 1,..., n. The graph G(G1,...,Gn) is obtained from G by attaching Gi to G at the vertex xi1 for i = 1,...,n. We give a characterization of G(G1,...,Gn) for being vertex decomposable. This generalizes a result due to Mousivand, Seyed Fakhari, and Yassemi.

APA, Harvard, Vancouver, ISO, and other styles

42

Ediz, Süleyman. "On R degrees of vertices and R indices of graphs." International Journal of Advanced Chemistry 5, no. 2 (August 6, 2017): 70. http://dx.doi.org/10.14419/ijac.v5i2.7973.

Full text

Abstract:

Topological indices have been used to modeling biological and chemical properties of molecules in quantitive structure property relationship studies and quantitive structure activity studies. All the degree based topological indices have been defined via classical degree concept. In this paper we define a novel degree concept for a vertex of a simple connected graph: R degree. And also we define R indices of a simple connected graph by using the R degree concept. We compute the R indices for well-known simple connected graphs such as paths, stars, complete graphs and cycles.

APA, Harvard, Vancouver, ISO, and other styles

43

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

44

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

45

FANG, XIN GUI, JIE WANG, and SANMING ZHOU. "CLASSIFICATION OF TETRAVALENT -TRANSITIVE NONNORMAL CAYLEY GRAPHS OF FINITE SIMPLE GROUPS." Bulletin of the Australian Mathematical Society 104, no. 2 (January 11, 2021): 263–71. http://dx.doi.org/10.1017/s0004972720001446.

Full text

Abstract:

AbstractA graph $\Gamma $ is called $(G, s)$ -arc-transitive if $G \le \text{Aut} (\Gamma )$ is transitive on the set of vertices of $\Gamma $ and the set of s-arcs of $\Gamma $ , where for an integer $s \ge 1$ an s-arc of $\Gamma $ is a sequence of $s+1$ vertices $(v_0,v_1,\ldots ,v_s)$ of $\Gamma $ such that $v_{i-1}$ and $v_i$ are adjacent for $1 \le i \le s$ and $v_{i-1}\ne v_{i+1}$ for $1 \le i \le s-1$ . A graph $\Gamma $ is called 2-transitive if it is $(\text{Aut} (\Gamma ), 2)$ -arc-transitive but not $(\text{Aut} (\Gamma ), 3)$ -arc-transitive. A Cayley graph $\Gamma $ of a group G is called normal if G is normal in $\text{Aut} (\Gamma )$ and nonnormal otherwise. Fang et al. [‘On edge transitive Cayley graphs of valency four’, European J. Combin.25 (2004), 1103–1116] proved that if $\Gamma $ is a tetravalent 2-transitive Cayley graph of a finite simple group G, then either $\Gamma $ is normal or G is one of the groups $\text{PSL}_2(11)$ , ${\rm M} _{11}$ , $\text{M} _{23}$ and $A_{11}$ . However, it was unknown whether $\Gamma $ is normal when G is one of these four groups. We answer this question by proving that among these four groups only $\text{M} _{11}$ produces connected tetravalent 2-transitive nonnormal Cayley graphs. We prove further that there are exactly two such graphs which are nonisomorphic and both are determined in the paper. As a consequence, the automorphism group of any connected tetravalent 2-transitive Cayley graph of any finite simple group is determined.

APA, Harvard, Vancouver, ISO, and other styles

46

Chen, X. Y., A. R. Moghaddamfar, and M. Zohourattar. "Some properties of various graphs associated with finite groups." Algebra and Discrete Mathematics 31, no. 2 (2021): 195–211. http://dx.doi.org/10.12958/adm1197.

Full text

Abstract:

In this paper we investigate some properties of the power graph and commuting graph associated with a finite group, using their tree-numbers. Among other things, it is shown that the simple group L2(7) can be characterized through the tree-number of its power graph. Moreover, the classification of groups with power-free decomposition is presented. Finally, we obtain an explicit formula concerning the tree-number of commuting graphs associated with the Suzuki simple groups.

APA, Harvard, Vancouver, ISO, and other styles

47

Koledin, Tamara, and Zoran Radosavljevic. "Unicyclic reflexive graphs with seven loaded vertices of the cycle." Filomat 23, no. 3 (2009): 257–68. http://dx.doi.org/10.2298/fil0903257k.

Full text

Abstract:

A simple graph is reflexive if the second largest eigenvalue of its (0, 1)- adjacency matrix does not exceed 2. A vertex of the cycle of unicyclic simple graph is said to be loaded if its degree is greater than 2. In this paper we establish that the length of the cycle of unicyclic reflexive graph with seven loaded vertices is at most 10 and find all such graphs with the length of the cycle 10, 9 and 8.

APA, Harvard, Vancouver, ISO, and other styles

48

Yap, H. P., and K. H. Chew. "Total chromatic number of graphs of high degree, II." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 53, no. 2 (October 1992): 219–28. http://dx.doi.org/10.1017/s1446788700035801.

Full text

Abstract:

AbstractWe prove Theorem 1: suppose G is a simple graph of order n having Δ(G) = n − k where k ≥ 5 and n ≥ max (13, 3k −3). If G contains an independent set of k − 3 vertices, then the TCC (Total Colouring Conjecture) is true. Applying Theorem 1, we also prove that the TCC is true for any simple graph G of order n having Δ(G) = n −5. The latter result together with some earlier results confirm that the TCC is true for all simple graphs whose maximum degree is at most four and for all simple graphs of order n having maximum degree at least n − 5.

APA, Harvard, Vancouver, ISO, and other styles

49

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

50

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

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!