Log in

Relevant bibliographies by topics / Combinatorics – Graph theory – Graph theory / Journal articles

To see the other types of publications on this topic, follow the link: Combinatorics – Graph theory – Graph theory.

Journal articles on the topic 'Combinatorics – Graph theory – Graph theory'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

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 'Combinatorics – Graph theory – Graph theory.'

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

Leversha, Gerry, John M. Harris, Jeffry L. Hirst, and Michael J. Mossinghoff. "Combinatorics and Graph Theory." Mathematical Gazette 86, no. 505 (March 2002): 177. http://dx.doi.org/10.2307/3621627.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Sebő, András, and Zoltán Szigeti. "Preface: Graph theory and combinatorics." Discrete Applied Mathematics 209 (August 2016): 1. http://dx.doi.org/10.1016/j.dam.2016.02.021.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

ILYUTKO, DENIS PETROVICH, and VASSILY OLEGOVICH MANTUROV. "INTRODUCTION TO GRAPH-LINK THEORY." Journal of Knot Theory and Its Ramifications 18, no. 06 (June 2009): 791–823. http://dx.doi.org/10.1142/s0218216509007191.

Full text

Abstract:

The present paper is an introduction to a combinatorial theory arising as a natural generalization of classical and virtual knot theory. There is a way to encode links by a class of "realizable" graphs. When passing to generic graphs with the same equivalence relations we get "graph-links". On one hand graph-links generalize the notion of virtual link, on the other hand they do not detect link mutations. We define the Jones polynomial for graph-links and prove its invariance. We also prove some a generalization of the Kauffman–Murasugi–Thistlethwaite theorem on "minimal diagrams" for graph-links.

APA, Harvard, Vancouver, ISO, and other styles

4

Bóna, Miklós. "Review of Combinatorics and graph theory." ACM SIGACT News 40, no. 3 (September 25, 2009): 37–39. http://dx.doi.org/10.1145/1620491.1620496.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

CONLEY, CLINTON T., ALEXANDER S. KECHRIS, and ROBIN D. TUCKER-DROB. "Ultraproducts of measure preserving actions and graph combinatorics." Ergodic Theory and Dynamical Systems 33, no. 2 (February 16, 2012): 334–74. http://dx.doi.org/10.1017/s0143385711001143.

Full text

Abstract:

AbstractUltraproducts of measure preserving actions of countable groups are used to study the graph combinatorics associated with such actions, including chromatic, independence and matching numbers. Applications are also given to the theory of random colorings of Cayley graphs and sofic actions and equivalence relations.

APA, Harvard, Vancouver, ISO, and other styles

6

CSIKVÁRI, PÉTER, and ZOLTÁN LÓRÁNT NAGY. "The Density Turán Problem." Combinatorics, Probability and Computing 21, no. 4 (February 29, 2012): 531–53. http://dx.doi.org/10.1017/s0963548312000016.

Full text

Abstract:

LetHbe a graph onnvertices and let the blow-up graphG[H] be defined as follows. We replace each vertexviofHby a clusterAiand connect some pairs of vertices ofAiandAjif (vi,vj) is an edge of the graphH. As usual, we define the edge density betweenAiandAjasWe study the following problem. Given densities γijfor each edge (i,j) ∈E(H), one has to decide whether there exists a blow-up graphG[H], with edge densities at least γij, such that one cannot choose a vertex from each cluster, so that the obtained graph is isomorphic toH,i.e., noHappears as a transversal inG[H]. We calldcrit(H) the maximal value for which there exists a blow-up graphG[H] with edge densitiesd(Ai,Aj)=dcrit(H) ((vi,vj) ∈E(H)) not containingHin the above sense. Our main goal is to determine the critical edge density and to characterize the extremal graphs.First, in the case of treeTwe give an efficient algorithm to decide whether a given set of edge densities ensures the existence of a transversalTin the blow-up graph. Then we give general bounds ondcrit(H) in terms of the maximal degree. In connection with the extremal structure, the so-called star decomposition is proved to give the best construction forH-transversal-free blow-up graphs for several graph classes. Our approach applies algebraic graph-theoretical, combinatorial and probabilistic tools.

APA, Harvard, Vancouver, ISO, and other styles

7

Stein, Maya. "Extremal infinite graph theory." Discrete Mathematics 311, no. 15 (August 2011): 1472–96. http://dx.doi.org/10.1016/j.disc.2010.12.018.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

ALON, NOGA. "Combinatorial Nullstellensatz." Combinatorics, Probability and Computing 8, no. 1-2 (January 1999): 7–29. http://dx.doi.org/10.1017/s0963548398003411.

Full text

Abstract:

We present a general algebraic technique and discuss some of its numerous applications in combinatorial number theory, in graph theory and in combinatorics. These applications include results in additive number theory and in the study of graph colouring problems. Many of these are known results, to which we present unified proofs, and some results are new.

APA, Harvard, Vancouver, ISO, and other styles

9

Dobrinen, Natasha. "The Ramsey theory of the universal homogeneous triangle-free graph." Journal of Mathematical Logic 20, no. 02 (January 28, 2020): 2050012. http://dx.doi.org/10.1142/s0219061320500129.

Full text

Abstract:

The universal homogeneous triangle-free graph, constructed by Henson [A family of countable homogeneous graphs, Pacific J. Math. 38(1) (1971) 69–83] and denoted [Formula: see text], is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős–Hajnal–Posá [Strong embeddings of graphs into coloured graphs, in Infinite and Finite Sets. Vol.[Formula: see text] , eds. A. Hajnal, R. Rado and V. Sós, Colloquia Mathematica Societatis János Bolyai, Vol. 10 (North-Holland, 1973), pp. 585–595] and culminating in work of Sauer [Coloring subgraphs of the Rado graph, Combinatorica 26(2) (2006) 231–253] and Laflamme–Sauer–Vuksanovic [Canonical partitions of universal structures, Combinatorica 26(2) (2006) 183–205], the Ramsey theory of [Formula: see text] had only progressed to bounds for vertex colorings [P. Komjáth and V. Rödl, Coloring of universal graphs, Graphs Combin. 2(1) (1986) 55–60] and edge colorings [N. Sauer, Edge partitions of the countable triangle free homogenous graph, Discrete Math. 185(1–3) (1998) 137–181]. This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph [Formula: see text], there is a finite number [Formula: see text] such that for any coloring of all copies of [Formula: see text] in [Formula: see text] into finitely many colors, there is a subgraph of [Formula: see text] which is again universal homogeneous triangle-free in which the coloring takes no more than [Formula: see text] colors. This is the first such result for a homogeneous structure omitting copies of some nontrivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code [Formula: see text] and the development of their Ramsey theory.

APA, Harvard, Vancouver, ISO, and other styles

10

Cvetkovic, Dragos, Pierre Hansen, and Vera Kovacevic-Vujcic. "On some interconnections between combinatorial optimization and extremal graph theory." Yugoslav Journal of Operations Research 14, no. 2 (2004): 147–54. http://dx.doi.org/10.2298/yjor0402147c.

Full text

Abstract:

The uniting feature of combinatorial optimization and extremal graph theory is that in both areas one should find extrema of a function defined in most cases on a finite set. While in combinatorial optimization the point is in developing efficient algorithms and heuristics for solving specified types of problems, the extremal graph theory deals with finding bounds for various graph invariants under some constraints and with constructing extremal graphs. We analyze by examples some interconnections and interactions of the two theories and propose some conclusions.

APA, Harvard, Vancouver, ISO, and other styles

11

Amit, Alon, and Nathan Linial. "Random Graph Coverings I: General Theory and Graph Connectivity." Combinatorica 22, no. 1 (January 1, 2002): 1–18. http://dx.doi.org/10.1007/s004930200000.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

NATH, MILAN, and SOMNATH PAUL. "GRAPH TRANSFORMATION AND DISTANCE SPECTRAL RADIUS." Discrete Mathematics, Algorithms and Applications 05, no. 03 (September 2013): 1350014. http://dx.doi.org/10.1142/s1793830913500146.

Full text

Abstract:

Trees are very common in the theory and applications of combinatorics. In this paper, we consider graphs whose underlying structure is a tree and study the behavior of the distance spectral radius under a graph transformation. As an application, we find the corona tree that maximizes the distance spectral radius among all corona trees with a fixed maximum degree. We also find the graph with minimal (maximal) distance spectral radius among all corona trees. Finally, we determine the graph with minimal distance spectral radius in a special class of corona trees.

APA, Harvard, Vancouver, ISO, and other styles

13

Pendavingh, Rudi, Quintijn Puite, and Gerhard J. Woeginger. "2-piercings via graph theory." Discrete Applied Mathematics 156, no. 18 (November 2008): 3510–12. http://dx.doi.org/10.1016/j.dam.2008.03.026.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Grohe, Martin, and Daniel Neuen. "Isomorphism, canonization, and definability for graphs of bounded rank width." Communications of the ACM 64, no. 5 (May 2021): 98–105. http://dx.doi.org/10.1145/3453943.

Full text

Abstract:

We investigate the interplay between the graph isomorphism problem, logical definability, and structural graph theory on a rich family of dense graph classes: graph classes of bounded rank width. We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3 k + 4) is a complete isomorphism test for the class of all graphs of rank width at most k. A consequence of our result is the first polynomial time canonization algorithm for graphs of bounded rank width. Our second main result addresses an open problem in descriptive complexity theory: we show that fixed-point logic with counting expresses precisely the polynomial time properties of graphs of bounded rank width.

APA, Harvard, Vancouver, ISO, and other styles

15

Piless, Vera. "Problems In Combinatorics and Graph Theory (Ioan Tomescu)." SIAM Review 29, no. 1 (March 1987): 164. http://dx.doi.org/10.1137/1029035.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

McKee, Terry A. "Subgraph trees in graph theory." Discrete Mathematics 270, no. 1-3 (August 2003): 3–12. http://dx.doi.org/10.1016/s0012-365x(03)00161-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Brouwer, A. E., and W. H. Haemers. "The Gewirtz Graph: An Exercise in the Theory of Graph Spectra." European Journal of Combinatorics 14, no. 5 (September 1993): 397–407. http://dx.doi.org/10.1006/eujc.1993.1044.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Alon, Noga, and P. Erdös. "An Application of Graph Theory to Additive Number Theory." European Journal of Combinatorics 6, no. 3 (September 1985): 201–3. http://dx.doi.org/10.1016/s0195-6698(85)80027-5.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Hosseini, Sayed Mohammad, Mahdi Davoudi Darareh, Shahrooz Janbaz, and Ali Zaghian. "An Adiabatic Quantum Algorithm for Determining Gracefulness of a Graph." Zeitschrift für Naturforschung A 72, no. 7 (July 26, 2017): 637–45. http://dx.doi.org/10.1515/zna-2017-0011.

Full text

Abstract:

AbstractGraph labelling is one of the noticed contexts in combinatorics and graph theory. Graceful labelling for a graph G with e edges, is to label the vertices of G with 0, 1, ℒ, e such that, if we specify to each edge the difference value between its two ends, then any of 1, 2, ℒ, e appears exactly once as an edge label. For a given graph, there are still few efficient classical algorithms that determine either it is graceful or not, even for trees – as a well-known class of graphs. In this paper, we introduce an adiabatic quantum algorithm, which for a graceful graph G finds a graceful labelling. Also, this algorithm can determine if G is not graceful. Numerical simulations of the algorithm reveal that its time complexity has a polynomial behaviour with the problem size up to the range of 15 qubits. A general sufficient condition for a combinatorial optimization problem to have a satisfying adiabatic solution is also derived.

APA, Harvard, Vancouver, ISO, and other styles

20

HUGGETT, STEPHEN. "ON TANGLES AND MATROIDS." Journal of Knot Theory and Its Ramifications 14, no. 07 (November 2005): 919–29. http://dx.doi.org/10.1142/s0218216505004147.

Full text

Abstract:

Given matroids M and N there are two operations M ⊕2 N and M ⊗ N. When M and N are the cycle matroids of planar graphs these operations have interesting interpretations on the corresponding link diagrams. In fact, given a planar graph there are two well-established methods of generating an alternating link diagram, and in each case the Tutte polynomial of the graph is related to a polynomial invariant (Jones or Homfly) of the link. Switching from one of these methods to the other corresponds in knot theory to tangle insertion in the link diagrams, and in combinatorics to the tensor product of the cycle matroids of the graphs.

APA, Harvard, Vancouver, ISO, and other styles

21

PANDA, SWARUP. "Inverses of bicyclic graphs." Electronic Journal of Linear Algebra 32 (February 6, 2017): 217–31. http://dx.doi.org/10.13001/1081-3810.3322.

Full text

Abstract:

A graph G is said to be nonsingular (resp., singular) if its adjacency matrix A(G) is nonsingular (resp., singular). The inverse of a nonsingular graph G is the unique weighted graph whose adjacency matrix is similar to the inverse of the adjacency matrix A(G) via a diagonal matrix of Â±1s. Consider connected bipartite graphs with unique perfect matchings such that the graph obtained by contracting all matching edges is also bipartite. In [C.D. Godsil. Inverses of trees. Combinatorica, 5(1):33â39, 1985.], Godsil proved that such graphs are invertible. He posed the question of characterizing the bipartite graphs with unique perfect matchings possessing inverses. In this article, Godsilâs question for the class of bicyclic graphs is answered.

APA, Harvard, Vancouver, ISO, and other styles

22

White, Arthur T. "Topological Graph Theory: A Personal Account." Electronic Notes in Discrete Mathematics 31 (August 2008): 5–15. http://dx.doi.org/10.1016/j.endm.2008.06.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Koster, Arie, and Vadim Lozin. "DIMAP Workshop on Algorithmic Graph Theory." Electronic Notes in Discrete Mathematics 32 (March 2009): 1. http://dx.doi.org/10.1016/j.endm.2009.02.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Walker, Richard, and Steven Skiena. "Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica." Mathematical Gazette 76, no. 476 (July 1992): 286. http://dx.doi.org/10.2307/3619148.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Cvetkovic, Dragos, and Slobodan Simic. "Towards a spectral theory of graphs based on the signless Laplacian, III." Applicable Analysis and Discrete Mathematics 4, no. 1 (2010): 156–66. http://dx.doi.org/10.2298/aadm1000001c.

Full text

Abstract:

This part of our work further extends our project of building a new spectral theory of graphs (based on the signless Laplacian) by some results on graph angles, by several comments and by a short survey of recent results.

APA, Harvard, Vancouver, ISO, and other styles

26

Quilliot, Alain. "A retraction problem in graph theory." Discrete Mathematics 54, no. 1 (March 1985): 61–71. http://dx.doi.org/10.1016/0012-365x(85)90062-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Keqin, Feng. "A problem on algebraic graph theory." Discrete Mathematics 54, no. 1 (March 1985): 107–9. http://dx.doi.org/10.1016/0012-365x(85)90067-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Erdös, P. "Two problems in extremal graph theory." Graphs and Combinatorics 2, no. 1 (December 1986): 189–90. http://dx.doi.org/10.1007/bf01788092.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Lehtonen, Erkko, and Tamás Waldhauser. "Associative spectra of graph algebras I." Journal of Algebraic Combinatorics 53, no. 3 (May 2021): 613–38. http://dx.doi.org/10.1007/s10801-020-01010-w.

Full text

Abstract:

AbstractAssociative spectra of graph algebras are examined with the help of homomorphisms of DFS trees. Undirected graphs are classified according to the associative spectra of their graph algebras; there are only three distinct possibilities: constant 1, powers of 2, and Catalan numbers. Associative and antiassociative digraphs are described, and associative spectra are determined for certain families of digraphs, such as paths, cycles, and graphs on two vertices.

APA, Harvard, Vancouver, ISO, and other styles

30

Arsic, Branko, Dragos Cvetkovic, Slobodan Simic, and Milan Skaric. "Graph spectral techniques in computer sciences." Applicable Analysis and Discrete Mathematics 6, no. 1 (2012): 1–30. http://dx.doi.org/10.2298/aadm111223025a.

Full text

Abstract:

We give a survey of graph spectral techniques used in computer sciences. The survey consists of a description of particular topics from the theory of graph spectra independently of the areas of Computer science in which they are used. We have described the applications of some important graph eigenvalues (spectral radius, algebraic connectivity, the least eigenvalue etc.), eigenvectors (principal eigenvector, Fiedler eigenvector and other), spectral reconstruction problems, spectra of random graphs, Hoffman polynomial, integral graphs etc. However, for each described spectral technique we indicate the fields in which it is used (e.g. in modelling and searching Internet, in computer vision, pattern recognition, data mining, multiprocessor systems, statistical databases, and in several other areas). We present some novel mathematical results (related to clustering and the Hoffman polynomial) as well.

APA, Harvard, Vancouver, ISO, and other styles

31

Dukes, Peter, and Amanda Malloch. "An existence theory for loopy graph decompositions." Journal of Combinatorial Designs 19, no. 4 (February 1, 2011): 280–89. http://dx.doi.org/10.1002/jcd.20280.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

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

33

Cvetkovic, Dragos. "Spectral recognition of graphs." Yugoslav Journal of Operations Research 22, no. 2 (2012): 145–61. http://dx.doi.org/10.2298/yjor120925025c.

Full text

Abstract:

At some time, in the childhood of spectral graph theory, it was conjectured that non-isomorphic graphs have different spectra, i.e. that graphs are characterized by their spectra. Very quickly this conjecture was refuted and numerous examples and families of non-isomorphic graphs with the same spectrum (cospectral graphs) were found. Still some graphs are characterized by their spectra and several mathematical papers are devoted to this topic. In applications to computer sciences, spectral graph theory is considered as very strong. The benefit of using graph spectra in treating graphs is that eigenvalues and eigenvectors of several graph matrices can be quickly computed. Spectral graph parameters contain a lot of information on the graph structure (both global and local) including some information on graph parameters that, in general, are computed by exponential algorithms. Moreover, in some applications in data mining, graph spectra are used to encode graphs themselves. The Euclidean distance between the eigenvalue sequences of two graphs on the same number of vertices is called the spectral distance of graphs. Some other spectral distances (also based on various graph matrices) have been considered as well. Two graphs are considered as similar if their spectral distance is small. If two graphs are at zero distance, they are cospectral. In this sense, cospectral graphs are similar. Other spectrally based measures of similarity between networks (not necessarily having the same number of vertices) have been used in Internet topology analysis, and in other areas. The notion of spectral distance enables the design of various meta-heuristic (e.g., tabu search, variable neighbourhood search) algorithms for constructing graphs with a given spectrum (spectral graph reconstruction). Several spectrally based pattern recognition problems appear in many areas (e.g., image segmentation in computer vision, alignment of protein-protein interaction networks in bio-informatics, recognizing hard instances for combinatorial optimization problems such as the travelling salesman problem). We give a survey of such and other graph spectral recognition techniques used in computer sciences.

APA, Harvard, Vancouver, ISO, and other styles

34

Halász, Veronika, and Zsolt Tuza. "Asymptotically optimal induced decompositions." Applicable Analysis and Discrete Mathematics 8, no. 2 (2014): 320–29. http://dx.doi.org/10.2298/aadm140718009h.

Full text

Abstract:

Solving a problem raised by Bondy and Szwarcfiter [J. Graph Theory, 72 (2013), 462-477] we prove that if the edge set of a graph G of order n can be decomposed into edge-disjoint induced copies of the path P4 or of the paw K4?P3, then the complement of G has at least cn3/2 edges. This lower bound is tight apart from the actual value of c, and completes the determination of asymptotic growth for the graphs with at most four vertices. More generally the lower bound cn3/2 holds for any graph without isolated vertices which is not a complete multipartite graph; but a linear upper bound is valid for any complete tripartite graph.

APA, Harvard, Vancouver, ISO, and other styles

35

Paulraja, P., and Kumar Sampath. "On hamiltonian decompositions of tensor products of graphs." Applicable Analysis and Discrete Mathematics 13, no. 1 (2019): 178–202. http://dx.doi.org/10.2298/aadm170803003p.

Full text

Abstract:

Finding a hamiltonian decomposition of G is one of the challenging problems in graph theory. We do not know for what classes of graphs G and H, their tensor product G x H is hamiltonian decomposable. In this paper, we have proved that, if G is a hamiltonian decomposable circulant graph with certain properties and H is a hamiltonian decomposable multigraph, then G x H is hamiltonian decomposable. In particular, tensor products of certain sparse hamiltonian decomposable circulant graphs are hamiltonian decomposable.

APA, Harvard, Vancouver, ISO, and other styles

36

Brooks, Josephine, Alvaro Carbonero, Joseph Vargas, Rigoberto Flórez, Brendan Rooney, and Darren Narayan. "Removing Symmetry in Circulant Graphs and Point-Block Incidence Graphs." Mathematics 9, no. 2 (January 14, 2021): 166. http://dx.doi.org/10.3390/math9020166.

Full text

Abstract:

An automorphism of a graph is a mapping of the vertices onto themselves such that connections between respective edges are preserved. A vertex v in a graph G is fixed if it is mapped to itself under every automorphism of G. The fixing number of a graph G is the minimum number of vertices, when fixed, fixes all of the vertices in G. The determination of fixing numbers is important as it can be useful in determining the group of automorphisms of a graph-a famous and difficult problem. Fixing numbers were introduced and initially studied by Gibbons and Laison, Erwin and Harary and Boutin. In this paper, we investigate fixing numbers for graphs with an underlying cyclic structure, which provides an inherent presence of symmetry. We first determine fixing numbers for circulant graphs, showing in many cases the fixing number is 2. However, we also show that circulant graphs with twins, which are pairs of vertices with the same neighbourhoods, have considerably higher fixing numbers. This is the first paper that investigates fixing numbers of point-block incidence graphs, which lie at the intersection of graph theory and combinatorial design theory. We also present a surprising result-identifying infinite families of graphs in which fixing any vertex fixes every vertex, thus removing all symmetries from the graph.

APA, Harvard, Vancouver, ISO, and other styles

37

Ramprasad, Ch, P. L. N. Varma, S. Satyanarayana, and N. Srinivasarao. "Vertex Degrees and Isomorphic Properties in Complement of an m-Polar Fuzzy Graph." Advances in Fuzzy Systems 2017 (2017): 1–9. http://dx.doi.org/10.1155/2017/3817469.

Full text

Abstract:

Computational intelligence and computer science rely on graph theory to solve combinatorial problems. Normal product and tensor product of an m-polar fuzzy graph have been introduced in this article. Degrees of vertices in various product graphs, like Cartesian product, composition, tensor product, and normal product, have been computed. Complement and μ-complement of an m-polar fuzzy graph are defined and some properties are studied. An application of an m-polar fuzzy graph is also presented in this article.

APA, Harvard, Vancouver, ISO, and other styles

38

MATIGNON, DANIEL. "COMBINATORICS AND FOUR BRIDGED KNOTS." Journal of Knot Theory and Its Ramifications 10, no. 04 (June 2001): 493–527. http://dx.doi.org/10.1142/s0218216501000974.

Full text

Abstract:

The ℝ P 3-Conjecture states a non-trivial knot in S 3 cannot yield ℝ P 3 by a Dehn surgery. Generically, in the knot-space S3-N(K), the intersection of a projective plane ℝP2 in ℝ P 3, and any 2-sphere S2 in S3 pierced by K, is a 1-complex which can be viewed as a graph in either the projective plane or the 2-sphere. Gordon and Luecke have used similar graphs arising as the intersection of two 2-spheres, to prove that a knot in S3 is determined by its complement. A part of this paper concerns some new combinatorial results on these graphs. They are considered as an unavoidable step towards showing that the ℝ P 3-Conjecture is true. Moreover, we use these results to prove that any non-trivial knot that could yield ℝ P 3 has at least five bridges.

APA, Harvard, Vancouver, ISO, and other styles

39

Mohar, Bojan. "Some Topological Methods in Graph Coloring Theory." Electronic Notes in Discrete Mathematics 5 (July 2000): 231–34. http://dx.doi.org/10.1016/s1571-0653(05)80172-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Conlon, David, Jacob Fox, and Benny Sudakov. "On two problems in graph Ramsey theory." Combinatorica 32, no. 5 (May 2012): 513–35. http://dx.doi.org/10.1007/s00493-012-2710-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Catlin, Paul A., and Hong-Jian Lai. "Supereulerian Graphs and the Petersen Graph." Journal of Combinatorial Theory, Series B 66, no. 1 (January 1996): 123–39. http://dx.doi.org/10.1006/jctb.1996.0009.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

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

43

Abdian, Ali Zeydi, and S. Morteza Mirafzal. "The spectral characterizations of the connected multicone graphs Kw ▽ LHS and Kw ▽ LGQ(3,9)." Discrete Mathematics, Algorithms and Applications 10, no. 02 (April 2018): 1850019. http://dx.doi.org/10.1142/s1793830918500192.

Full text

Abstract:

In the past decades, graphs that are determined by their spectrum have received much more and more attention, since they have been applied to several fields, such as randomized algorithms, combinatorial optimization problems and machine learning. An important part of spectral graph theory is devoted to determining whether given graphs or classes of graphs are determined by their spectra or not. So, finding and introducing any class of graphs which are determined by their spectra can be an interesting and important problem. The main aim of this study is to characterize two classes of multicone graphs which are determined by their adjacency, Laplacian and signless Laplacian spectra. A multicone graph is defined to be the join of a clique and a regular graph. Let [Formula: see text] denote a complete graph on [Formula: see text] vertices. In the paper, we show that multicone graphs [Formula: see text] and [Formula: see text] are determined by both their adjacency spectra and their Laplacian spectra, where [Formula: see text] and [Formula: see text] denote the Local Higman–Sims graph and the Local [Formula: see text] graph, respectively. In addition, we prove that these multicone graphs are determined by their signless Laplacian spectra.

APA, Harvard, Vancouver, ISO, and other styles

44

Nešetřil, Jaroslav, and André Raspaud. "European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009)." Electronic Notes in Discrete Mathematics 34 (August 2009): 1–8. http://dx.doi.org/10.1016/j.endm.2009.07.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

45

Sciriha, Irene, Josef Lauri, John Baptist Gauci, and Peter Borg. "Preface: The Second Malta Conference in Graph Theory and Combinatorics." Discrete Applied Mathematics 266 (August 2019): 1–2. http://dx.doi.org/10.1016/j.dam.2019.05.016.

Full text

APA, Harvard, Vancouver, ISO, and other styles

46

Erdös, P., A. Meir, V. T. Sós, and P. Turán. "On some applications of graph theory, I." Discrete Mathematics 306, no. 10-11 (May 2006): 853–66. http://dx.doi.org/10.1016/j.disc.2006.03.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Liu, Shunyi. "Generalized Permanental Polynomials of Graphs." Symmetry 11, no. 2 (February 16, 2019): 242. http://dx.doi.org/10.3390/sym11020242.

Full text

Abstract:

The search for complete graph invariants is an important problem in graph theory and computer science. Two networks with a different structure can be distinguished from each other by complete graph invariants. In order to find a complete graph invariant, we introduce the generalized permanental polynomials of graphs. Let G be a graph with adjacency matrix A ( G ) and degree matrix D ( G ) . The generalized permanental polynomial of G is defined by P G ( x , μ ) = per ( x I − ( A ( G ) − μ D ( G ) ) ) . In this paper, we compute the generalized permanental polynomials for all graphs on at most 10 vertices, and we count the numbers of such graphs for which there is another graph with the same generalized permanental polynomial. The present data show that the generalized permanental polynomial is quite efficient for distinguishing graphs. Furthermore, we can write P G ( x , μ ) in the coefficient form ∑ i = 0 n c μ i ( G ) x n − i and obtain the combinatorial expressions for the first five coefficients c μ i ( G ) ( i = 0 , 1 , ⋯ , 4 ) of P G ( x , μ ) .

APA, Harvard, Vancouver, ISO, and other styles

48

N. K, Geetha. "Combinatorial Theory of a Complete Graph K5." IOSR Journal of Mathematics 10, no. 5 (2014): 10–12. http://dx.doi.org/10.9790/5728-10551012.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

"Combinatorics and graph theory." Choice Reviews Online 38, no. 08 (April 1, 2001): 38–4505. http://dx.doi.org/10.5860/choice.38-4505.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Wang, Zhen, and Zhixi Wang. "The Tripartite Separability of Density Matrices of Graphs." Electronic Journal of Combinatorics 14, no. 1 (May 23, 2007). http://dx.doi.org/10.37236/958.

Full text

Abstract:

The density matrix of a graph is the combinatorial laplacian matrix of a graph normalized to have unit trace. In this paper we generalize the entanglement properties of mixed density matrices from combinatorial laplacian matrices of graphs discussed in Braunstein et al. [Annals of Combinatorics, 10 (2006) 291] to tripartite states. Then we prove that the degree condition defined in Braunstein et al. [Phys. Rev. A, 73 (2006) 012320] is sufficient and necessary for the tripartite separability of the density matrix of a nearest point graph.

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!