Relevant bibliographies by topics / Graphe n-partie / Journal articles
To see the other types of publications on this topic, follow the link: Graphe n-partie.

Journal articles on the topic 'Graphe n-partie'

Author: Grafiati
Published: 25 May 2024
Last updated: 31 July 2025

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 n-partie.'

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

Gervacio, Severino V. "Resistance distance in complete n-partite graphs." Discrete Applied Mathematics 203 (April 2016): 53–61. http://dx.doi.org/10.1016/j.dam.2015.09.017.

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

Qingxue, Huang. "Complete multipartite decompositions of complete graphs and complete n-partite graphs." Applied Mathematics-A Journal of Chinese Universities 18, no. 3 (2003): 352–60. http://dx.doi.org/10.1007/s11766-003-0061-y.

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

Hwang, Shiow-Fen, and Gerard J. Chang. "Edge domatic numbers of complete n- partite graphs." Graphs and Combinatorics 10, no. 2-4 (1994): 241–48. http://dx.doi.org/10.1007/bf02986672.

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

Lam, Peter Che Bor, Wai Chee Shiu, Chong Sze Tong, and Zhong Fu Zhang. "On the equitable chromatic number of complete n-partite graphs." Discrete Applied Mathematics 113, no. 2-3 (2001): 307–10. http://dx.doi.org/10.1016/s0166-218x(00)00296-1.

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

Poojary, Raksha, Arathi Bhat K, Manjunatha Prasad Karantha, S. Arumugam, and Ivan Gutman. "Characterizing Graphs with Nullity n-4." match Communications in Mathematical and in Computer Chemistry 89, no. 3 (2023): 631–42. http://dx.doi.org/10.46793/match.89-3.631p.

Full text
Abstract:
The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in the spectrum of G. A unified approach is presented for the characterization of graphs of order n with η(G) = n−4. All known results on trees, unicyclic graphs, bicyclic graphs, graphs with minimum degree 1, and r-partite graphs, for which η(G) = n−4 are shown to be corollaries of a theorem of Chang, Huang and Yeh that characterizes all graphs with nullity n − 4.
APA, Harvard, Vancouver, ISO, and other styles
6

YUSTER, RAPHAEL. "Independent Transversals and Independent Coverings in Sparse Partite Graphs." Combinatorics, Probability and Computing 6, no. 1 (1997): 115–25. http://dx.doi.org/10.1017/s0963548396002763.

Full text
Abstract:
An [n, k, r]-partite graph is a graph whose vertex set, V, can be partitioned into n pairwise-disjoint independent sets, V1, …, Vn, each containing exactly k vertices, and the subgraph induced by Vi ∪ Vj contains exactly r independent edges, for 1 [les ] i < j [les ] n. An independent transversal in an [n, k, r]-partite graph is an independent set, T, consisting of n vertices, one from each Vi. An independent covering is a set of k pairwise-disjoint independent transversals. Let t(k, r) denote the maximal n for which every [n, k, r]-partite graph contains an independent transversal. Let c(k
APA, Harvard, Vancouver, ISO, and other styles
7

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

Full text
Abstract:
An equitable k-coloring of a graph G is a proper k-coloring of G such that the sizes of any two color classes differ by at most one. An equitable (q,r)-tree-coloring of a graph G is an equitable q-coloring of G such that the subgraph induced by each color class is a forest of maximum degree at most r. Let the strong equitable vertex r-arboricity of a graph G, denoted by var≡(G), be the minimum p such that G has an equitable (q,r)-tree-coloring for every q≥p. The values of va1≡(Kn,n) were investigated by Tao and Lin and Wu, Zhang, and Li where exact values of va1≡(Kn,n) were found in some speci
APA, Harvard, Vancouver, ISO, and other styles
8

Wang, Chuan, Hua Zhang, Liang Yang, Xiaochun Cao, and Hongkai Xiong. "Multiple Semantic Matching on Augmented $N$ -Partite Graph for Object Co-Segmentation." IEEE Transactions on Image Processing 26, no. 12 (2017): 5825–39. http://dx.doi.org/10.1109/tip.2017.2750410.

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

Rahbarnia, F., and M. Moaied. "An upper bound for the equitable chromatic number of complete n-partite graphs." Journal of Nonlinear Analysis and Application 2014 (2014): 1–7. http://dx.doi.org/10.5899/2014/jnaa-00090.

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

PAULRAJA, P., and V. SHEEBA AGNES. "CONNECTIVITY OF TENSOR PRODUCT OF GRAPHS." Discrete Mathematics, Algorithms and Applications 05, no. 04 (2013): 1350023. http://dx.doi.org/10.1142/s1793830913500237.

Full text
Abstract:
In this paper, we determine the connectivity of G × Kr0,r1,…,rn-1, where × denotes the tensor product of graphs and Kr0,r1,…,rn-1 denotes the complete n-partite graph with [Formula: see text], and n ≥ 3. The main result of this paper deduces the main result of the paper appeared in Discrete Math. 311 (2011) 2563–2565 as a corollary.
APA, Harvard, Vancouver, ISO, and other styles
11

Kayibi, Koko K., U. Samee, Shariefuddin Pirzada, and Muhammad Ali Khan. "Sampling k-partite graphs with a given degree sequence." Acta Universitatis Sapientiae, Informatica 10, no. 2 (2018): 183–217. http://dx.doi.org/10.2478/ausi-2018-0010.

Full text
Abstract:
Abstract The authors in the paper [15] presented an algorithm that generates uniformly all the bipartite realizations and the other algorithm that generates uniformly all the simple bipartite realizations whenever A is a bipartite degree sequence of a simple graph. The running time of both algorithms is 𝒪(m),where ${\rm{m}} = {1 \over 2}\sum\nolimits_{\rm {i} = 1}^n {{ \rm{a}_\rm {i}}}$ . Let A =(A1 : A2 : ... : Ak) be a k-partite degree sequence of a simple graph, where Ai has ni entries such that ∑ni=n. In the present article, we give a generalized algorithm that generates uniformly all the
APA, Harvard, Vancouver, ISO, and other styles
12

Agnes, Sheeba. "Degree distance of tensor product and strong product of graphs." Filomat 28, no. 10 (2014): 2185–98. http://dx.doi.org/10.2298/fil1410185a.

Full text
Abstract:
In this paper, we determine the degree distance of G x Kr0,r1,...,rn-1 and G ? Kr0,r1,...,rn-1, where x and ? denote the tensor product and strong product of graphs, respectively, and Kr0,r1,...,rn-1 denotes the complete multipartite graph with partite sets V0,V1,...,Vn-1 where |Vj| = rj, 0 ? j ? n - 1 and n ? 3. Using the formulae obtained here, we have obtained the exact value of the degree distance of some classes of graphs.
APA, Harvard, Vancouver, ISO, and other styles
13

BLAIN, PAUL, GARRY BOWLIN, THOMAS FLEMING, JOEL FOISY, JACOB HENDRICKS, and JASON LACOMBE. "SOME RESULTS ON INTRINSICALLY KNOTTED GRAPHS." Journal of Knot Theory and Its Ramifications 16, no. 06 (2007): 749–60. http://dx.doi.org/10.1142/s021821650700552x.

Full text
Abstract:
We show that graphs of the form G * K2 are intrinsically knotted if and only if G is nonplanar. This can be extended to show that G * K5m+1 is intrinsically (m + 2)-linked when G is nonplanar. We also apply this result to classify all complete n-partite graphs with respect to intrinsic knotting and show that this family does not produce any new minor-minimal examples. Finally, we categorize all minor-minimal intrinsically knotted graphs on 8 or fewer vertices.
APA, Harvard, Vancouver, ISO, and other styles
14

Chen, Xiaolin, and Huishu Lian. "Extremal Matching Energy and the Largest Matching Root of Complete Multipartite Graphs." Complexity 2019 (April 16, 2019): 1–7. http://dx.doi.org/10.1155/2019/9728976.

Full text
Abstract:
The matching energy ME(G) of a graph G was introduced by Gutman and Wagner, which is defined as the sum of the absolute values of the roots of the matching polynomial m(G,x). The largest matching root λ1(G) is the largest root of the matching polynomial m(G,x). Let Kn1,n2,…,nr denote the complete r-partite graph with order n=n1+n2+…+nr, where r>1. In this paper, we prove that, for the given values n and r, both the matching energy ME(G) and the largest matching root λ1(G) of complete r-partite graphs are minimal for complete split graph CS(n,r-1) and are maximal for Turán graph T(n,r).
APA, Harvard, Vancouver, ISO, and other styles
15

ALLEN, PETER, JULIA BÖTTCHER, YOSHIHARU KOHAYAKAWA, and BARNABY ROBERTS. "Triangle-Free Subgraphs of Random Graphs." Combinatorics, Probability and Computing 27, no. 2 (2017): 141–61. http://dx.doi.org/10.1017/s0963548317000219.

Full text
Abstract:
Recently there has been much interest in studying random graph analogues of well-known classical results in extremal graph theory. Here we follow this trend and investigate the structure of triangle-free subgraphs of G(n, p) with high minimum degree. We prove that asymptotically almost surely each triangle-free spanning subgraph of G(n, p) with minimum degree at least (2/5 + o(1))pn is (p−1n)-close to bipartite, and each spanning triangle-free subgraph of G(n, p) with minimum degree at least (1/3 + ϵ)pn is O(p−1n)-close to r-partite for some r = r(ϵ). These are random graph analogues of a resu
APA, Harvard, Vancouver, ISO, and other styles
16

Alnefaie, Kholood, Nanggom Gammi, Saifur Rahman, and Shakir Ali. "On Zero-Divisor Graphs of Zn When n Is Square-Free." Axioms 14, no. 3 (2025): 180. https://doi.org/10.3390/axioms14030180.

Full text
Abstract:
In this article, some properties of the zero-divisor graph Γ(Zn) are investigated when n is a square-free positive integer. It is shown that the zero-divisor graph Γ(Zn) of ring Zn is a (2k−2)-partite graph when the prime decomposition of n contains k distinct square-free primes using the method of congruence relation. We present some examples, accompanied by graphic representations, to achieve the desired results. It is also obtained that the zero-divisor graph Γ(Zn) is Eulerian if n is a square-free odd integer. Since Zn is a semisimple ring when n is square-free, the results can be generali
APA, Harvard, Vancouver, ISO, and other styles
17

Alon, Noga. "Choice Numbers of Graphs: a Probabilistic Approach." Combinatorics, Probability and Computing 1, no. 2 (1992): 107–14. http://dx.doi.org/10.1017/s0963548300000122.

Full text
Abstract:
The choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). By applying probabilistic methods, it is shown that there are two positive constants c1 and c2 such that for all m ≥ 2 and r ≥ 2 the choice number of the complete r-partite graph with m vertices in each vertex class is between c1r log m and c2r log m. This supplies the solutions of two problems of Erdős, Rubin and Taylor, as it implies that the choice number of almost all the gra
APA, Harvard, Vancouver, ISO, and other styles
18

Koponen, Vera. "A Limit Law of Almost l-partite Graphs." Journal of Symbolic Logic 78, no. 3 (2013): 911–36. http://dx.doi.org/10.2178/jsl.7803110.

Full text
Abstract:
AbstractFor integers l ≥ 1, d ≥ 0 we study (undirected) graphs with vertices 1, …, n such that the vertices can be partitioned into l parts such that every vertex has at most d neighbours in its own part. The set of all such graphs is denoted Pn (l, d). We prove a labelled first-order limit law, i.e., for every first-order sentence φ, the proportion of graphs in Pn (l, d) that satisfy φ converges as n → ∞. By combining this result with a result of Hundack, Prömel and Steger [12] we also prove that if 1 ≤ s1 ≤ … ≤ sl are integers, then Forb() has a labelled first-order limit law, where Forb() d
APA, Harvard, Vancouver, ISO, and other styles
19

Wang, Fu-Hsing. "The lower and upper forcing geodetic numbers of completen-partite graphs,n-dimensional meshes and tori." International Journal of Computer Mathematics 87, no. 12 (2010): 2677–87. http://dx.doi.org/10.1080/00207160903003302.

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

BALOGH, JÓZSEF, CHOONGBUM LEE, and WOJCIECH SAMOTIJ. "Corrádi and Hajnal's Theorem for Sparse Random Graphs." Combinatorics, Probability and Computing 21, no. 1-2 (2012): 23–55. http://dx.doi.org/10.1017/s0963548311000642.

Full text
Abstract:
In this paper we extend a classical theorem of Corrádi and Hajnal into the setting of sparse random graphs. We show that ifp(n) ≫ (logn/n)1/2, then asymptotically almost surely every subgraph ofG(n,p) with minimum degree at least (2/3 +o(1))npcontains a triangle packing that covers all but at mostO(p−2) vertices. Moreover, the assumption onpis optimal up to the (logn)1/2factor and the presence of the set ofO(p−2) uncovered vertices is indispensable. The main ingredient in the proof, which might be of independent interest, is an embedding theorem which says that if one imposes certain natural r
APA, Harvard, Vancouver, ISO, and other styles
21

Zhang, Yameng, and Xia Zhang. "On the fractional total domatic numbers of incidence graphs." Mathematical Modelling and Control 3, no. 1 (2023): 73–79. http://dx.doi.org/10.3934/mmc.2023007.

Full text
Abstract:
<abstract><p>For a hypergraph $ H $ with vertex set $ X $ and edge set $ Y $, the incidence graph of hypergraph $ H $ is a bipartite graph $ I(H) = (X, Y, E) $, where $ xy\in E $ if and only if $ x\in X $, $ y\in Y $ and $ x\in y $. A total dominating set of graph $ G $ is a vertex subset that intersects every open neighborhood of $ G $. Let $ \mathscr{M} $ be a family of (not necessarily distinct) total dominating sets of $ G $ and $ r_{\mathscr{M}} $ be the maximum times that any vertex of $ G $ appears in $ \mathscr{M} $. The fractional domatic number $ G $ is defined as $ FTD(G
APA, Harvard, Vancouver, ISO, and other styles
22

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 dimensio
APA, Harvard, Vancouver, ISO, and other styles
23

Yang, Ruosong, and Ligong Wang. "Distance integral complete r-partite graphs." Filomat 29, no. 4 (2015): 739–49. http://dx.doi.org/10.2298/fil1504739y.

Full text
Abstract:
Let D(G)=(dij)nxn denote the distance matrix of a connected graph G with order n, where dij is equal to the distance between vertices vi and vj in G. A graph is called distance integral if all eigenvalues of its distance matrix are integers. In this paper, we investigate distance integral complete r-partite graphs Kp1,p2,...,pr = Ka1?p1,a2?p2,...,as?ps and give a sufficient and necessary condition for Ka1?p1,a2?p2,...,as?ps to be distance integral, from which we construct infinitely many new classes of distance integral graphs with s = 1,2,3,4. Finally, we propose two basic open problems for f
APA, Harvard, Vancouver, ISO, and other styles
24

MUBAYI, DHRUV. "Some Exact Results and New Asymptotics for Hypergraph Turán Numbers." Combinatorics, Probability and Computing 11, no. 3 (2002): 299–309. http://dx.doi.org/10.1017/s0963548301005028.

Full text
Abstract:
Given a family [Fscr ] of r-graphs, let ex(n, [Fscr ]) be the maximum number of edges in an n-vertex r-graph containing no member of [Fscr ]. Let C(r)4 denote the family of r-graphs with distinct edges A, B, C, D, such that A ∩ B = C ∩ D = Ø and A ∪ B = C ∪ D. For s1 [les ] … [les ] sr, let K(r) (s1,…,sr) be the complete r-partite r-graph with parts of sizes s1,…,sr.Füredi conjectured over 15 years ago that ex(n,C(3)4) [les ] (n2) for sufficiently large n. We prove the weaker resultex(n, {C(3)4, K(3)(1,2,4)}) [les ] (n2).Generalizing a well-known conjecture for the Turán number of bipartite gr
APA, Harvard, Vancouver, ISO, and other styles
25

C., Sujatha, and Manickam A. "Continuous Monotonic Decomposition of Some Standard Graphs by using an Algorithm." International Journal of Basic Sciences and Applied Computing (IJBSAC) 2, no. 8 (2019): 6–9. https://doi.org/10.35940/ijbsac.H0103.072819.

Full text
Abstract:
In this paper we elaborate an algorithm to compute the necessary and sufficient conditions for the continuous monotonic star decomposition of the bipartite graph Km,r and the number of vertices and the number of disjoint sets. Also an algorithm to find the tensor product of Pn  Ps has continuous monotonic path decomposition. Finally we conclude that in this paper the results described above are complete bipartite graphs that accept Continuous monotonic star decomposition. There are many other classes of complete tripartite graphs that accept Continuous monotonic star decomposition. In this re
APA, Harvard, Vancouver, ISO, and other styles
26

K. G., Nagarathnamma, and Leena N. Shenoy. "On Hamilton Laceability and Random Hamiltonian-t*– Laceablity of Total Transformation Graph G-++." Journal of Dynamics and Control 9, no. 5 (2025): 36–45. https://doi.org/10.71058/jodac.v9i5004.

Full text
Abstract:
A connected graph is called Hamiltonian if contains a spanning cycle and if a graph contains a spanning path between arbitrary pair of its vertices is called Hamilton-connected. A bipartite graph is called Hamilton-laceable if there exist Hamiltonian path between vertices of different partite sets and a graph is random Hamiltonian-– laceable if there exists a Hamiltonian path for at least one pair for distance. In this paper, we have studied the Hamiltonian laceble and random Hamiltonian-– laceable graphs of total transformation graph of graphs viz. path , cycle , complete bipartite graph , n-
APA, Harvard, Vancouver, ISO, and other styles
27

NIKIFOROV, VLADIMIR. "A Spectral Erdős–Stone–Bollobás Theorem." Combinatorics, Probability and Computing 18, no. 3 (2009): 455–58. http://dx.doi.org/10.1017/s0963548309009687.

Full text
Abstract:
Let r ≥ 3 and (c/rr)r log n ≥ 1. If G is a graph of order n and its largest eigenvalue μ(G) satisfies then G contains a complete r-partite subgraph with r − 1 parts of size ⌊(c/rr)r log n⌋ and one part of size greater than n1−cr−1.This result implies the Erdős–Stone–Bollobás theorem, the essential quantitative form of the Erdős–Stone theorem. Another easy consequence is that if F1, F2, . . . are r-chromatic graphs satisfying v(Fn) = o(log n), then
APA, Harvard, Vancouver, ISO, and other styles
28

Chin, Seungbeom, Marcin Karczewski, and Yong-Su Kim. "Heralded Optical Entanglement Generation via the Graph Picture of Linear Quantum Networks." Quantum 8 (December 18, 2024): 1572. https://doi.org/10.22331/q-2024-12-18-1572.

Full text
Abstract:
Non-destructive heralded entanglement with photons is a valuable resource for quantum information processing. However, they generally entail ancillary particles and modes that amplify the circuit intricacy. To address this challenge, a recent work \cite{chin2024shortcut} introduced a graph approach for creating multipartite entanglements with boson subtractions. Nonetheless, it remains an essential intermediate step toward practical heralded schemes: the proposition of heralded subtraction operators in bosonic linear quantum networks. This research establishes comprehensive translation rules f
APA, Harvard, Vancouver, ISO, and other styles
29

Huda, Muhammad Nurul, and Hartono Hartono. "Metric Dimension of Banded-Turán Graph." PYTHAGORAS Jurnal Pendidikan Matematika 19, no. 1 (2024): 18–26. https://doi.org/10.21831/pythagoras.v19i1.68025.

Full text
Abstract:
Given a graph G=(V(G),E(G)). Let S={s1,...,sk} be an ordered subset of V(G). Consider a vertex x, a coordinate of x with respect to S is represented as r(x|S)=(d(x,s1),...,d(x,sk)) where d(x,si) equals the number of edges in the shortest path between x and si for i=1,...,k. The minimum value of k such that for every x has distinct coordinate is called metric dimension of G. Turán graph T(n,r), n=r=2 is a subgraph of complete r-partite graph on n vertices having property that the difference of cardinality of any two distinct classes is at most one. In this paper, we build a new graph namely a b
APA, Harvard, Vancouver, ISO, and other styles
30

LO, ALLAN, and KLAS MARKSTRÖM. "A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs." Combinatorics, Probability and Computing 22, no. 1 (2012): 97–111. http://dx.doi.org/10.1017/s096354831200048x.

Full text
Abstract:
A perfect Kt-matching in a graph G is a spanning subgraph consisting of vertex-disjoint copies of Kt. A classic theorem of Hajnal and Szemerédi states that if G is a graph of order n with minimum degree δ(G) ≥ (t − 1)n/t and t|n, then G contains a perfect Kt-matching. Let G be a t-partite graph with vertex classes V1, …, Vt each of size n. We show that, for any γ > 0, if every vertex x ∈ Vi is joined to at least $\bigl ((t-1)/t + \gamma \bigr )n$ vertices of Vj for each j ≠ i, then G contains a perfect Kt-matching, provided n is large enough. Thus, we verify a conjecture of Fischer [6] asym
APA, Harvard, Vancouver, ISO, and other styles
31

Das, Joyentanuj, and Sumit Mohanty. "Inverse of the squared distance matrix of a complete multipartite graph." Electronic Journal of Linear Algebra 40 (July 15, 2024): 475–90. http://dx.doi.org/10.13001/ela.2024.8283.

Full text
Abstract:
Let $G$ be a connected graph on $n$ vertices and $d_{ij}$ be the length of the shortest path between vertices $i$ and $j$ in $G$. We set $d_{ii}=0$ for every vertex $i$ in $G$. The squared distance matrix $\Delta(G)$ of $G$ is the $n\times n$ matrix with $(i,j)^{th}$ entry equal to $0$ if $i = j$ and equal to $d_{ij}^2$ if $i \neq j$. For a given complete $t$-partite graph $K_{n_1,n_2,\cdots,n_t}$ on $n=\sum_{i=1}^t n_i$ vertices, under some condition we find the inverse $\Delta(K_{n_1,n_2,\cdots,n_t})^{-1}$ as a rank-one perturbation of a symmetric Laplacian-like matrix $\mathcal{L}$ with $\t
APA, Harvard, Vancouver, ISO, and other styles
32

Bennett, Patrick, Andrzej Dudek, Bernard Lidický, and Oleg Pikhurko. "Minimizing the number of 5-cycles in graphs with given edge-density." Combinatorics, Probability and Computing 29, no. 1 (2019): 44–67. http://dx.doi.org/10.1017/s0963548319000257.

Full text
Abstract:
AbstractMotivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle C5. We show that every graph of order n and size $ (1 - 1/k) \left( {\matrix{n \cr 2 }} \right) $, where k ≥ 3 is an integer, contains at least $$({1 \over {10}} - {1 \over {2k}} + {1 \over {{k^2}}} - {1 \over {{k^3}}} + {2 \over {5{k^4}}}){n^5} + o({n^5})$$ copies of C5. This bound is optimal, since a matching upper bound is given by the balanced complete k-partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An
APA, Harvard, Vancouver, ISO, and other styles
33

Lingas, Andrzej, Mateusz Miotk, Jerzy Topp, and Paweł Żyliński. "Graphs with equal domination and covering numbers." Journal of Combinatorial Optimization 39, no. 1 (2019): 55–71. http://dx.doi.org/10.1007/s10878-019-00454-6.

Full text
Abstract:
Abstract A dominating set of a graph G is a set $$D\subseteq V_G$$D⊆VG such that every vertex in $$V_G-D$$VG-D is adjacent to at least one vertex in D, and the domination number $$\gamma (G)$$γ(G) of G is the minimum cardinality of a dominating set of G. A set $$C\subseteq V_G$$C⊆VG is a covering set of G if every edge of G has at least one vertex in C. The covering number $$\beta (G)$$β(G) of G is the minimum cardinality of a covering set of G. The set of connected graphs G for which $$\gamma (G)=\beta (G)$$γ(G)=β(G) is denoted by $${\mathcal {C}}_{\gamma =\beta }$$Cγ=β, whereas $${\mathcal {
APA, Harvard, Vancouver, ISO, and other styles
34

Gao, Fang, Xiaoxin Li, Kai Zhou, and Jia-Bao Liu. "The Extremal Graphs of Some Topological Indices with Given Vertex k-Partiteness." Mathematics 6, no. 11 (2018): 271. http://dx.doi.org/10.3390/math6110271.

Full text
Abstract:
The vertex k-partiteness of graph G is defined as the fewest number of vertices whose deletion from G yields a k-partite graph. In this paper, we characterize the extremal value of the reformulated first Zagreb index, the multiplicative-sum Zagreb index, the general Laplacian-energy-like invariant, the general zeroth-order Randić index, and the modified-Wiener index among graphs of order n with vertex k-partiteness not more than m .
APA, Harvard, Vancouver, ISO, and other styles
35

Gao, Wei, Jie Han, and Yi Zhao. "Codegree Conditions for Tiling Complete k-Partite k-Graphs and Loose Cycles." Combinatorics, Probability and Computing 28, no. 06 (2019): 840–70. http://dx.doi.org/10.1017/s096354831900021x.

Full text
Abstract:
AbstractGiven two k-graphs (k-uniform hypergraphs) F and H, a perfect F-tiling (or F-factor) in H is a set of vertex-disjoint copies of F that together cover the vertex set of H. For all complete k-partite k-graphs K, Mycroft proved a minimum codegree condition that guarantees a K-factor in an n-vertex k-graph, which is tight up to an error term o(n). In this paper we improve the error term in Mycroft’s result to a sublinear term that relates to the Turán number of K when the differences of the sizes of the vertex classes of K are co-prime. Furthermore, we find a construction which shows that
APA, Harvard, Vancouver, ISO, and other styles
36

JANZING, DOMINIK, PAWEL WOCJAN, and THOMAS BETH. "ON THE COMPUTATIONAL POWER OF PHYSICAL INTERACTIONS: BOUNDS ON THE NUMBER OF TIME STEPS FOR SIMULATING ARBITRARY INTERACTION GRAPHS." International Journal of Foundations of Computer Science 14, no. 05 (2003): 889–903. http://dx.doi.org/10.1142/s0129054103002072.

Full text
Abstract:
The most popular model of quantum computation is the quantum circuit model using single and two qubit gates as elementary transformations. Definitions of quantum complexity usually refer to this model. In contrast, we consider the physical interactions among the qubits as the basic computational resource that allows to carry out complex transformations on the quantum register. One method to compare the computational power of different interactions is to examine the complexity of the so-called mutual simulation of interaction Hamiltonians. The physical interaction can simulate other interaction
APA, Harvard, Vancouver, ISO, and other styles
37

Bhat, K. Arathi, and G. Sudhakara. "Commuting decomposition of Kn1,n2,...,nk through realization of the product A(G)A(GPk )." Special Matrices 6, no. 1 (2018): 343–56. http://dx.doi.org/10.1515/spma-2018-0028.

Full text
Abstract:
Abstract In this paper, we introduce the notion of perfect matching property for a k-partition of vertex set of given graph. We consider nontrivial graphs G and GPk , the k-complement of graph G with respect to a kpartition of V(G), to prove that A(G)A(GPk ) is realizable as a graph if and only if P satis_es perfect matching property. For A(G)A(GPk ) = A(Γ) for some graph Γ, we obtain graph parameters such as chromatic number, domination number etc., for those graphs and characterization of P is given for which GPk and Γ are isomorphic. Given a 1-factor graph G with 2n vertices, we propose a p
APA, Harvard, Vancouver, ISO, and other styles
38

KEEVASH, PETER, and WILLIAM LOCHET. "The Structure of Typical Eye-Free Graphs and a Turán-Type Result for Two Weighted Colours." Combinatorics, Probability and Computing 26, no. 6 (2017): 886–910. http://dx.doi.org/10.1017/s0963548317000293.

Full text
Abstract:
The (a,b)-eye is the graph Ia,b = Ka+b \ Kb obtained by deleting the edges of a clique of size b from a clique of size a+b. We show that for any a,b ≥ 2 and p ∈ (0,1), if we condition the random graph G ~ G(n,p) on having no induced copy of Ia,b, then with high probability G is close to an a-partite graph or the complement of a (b−1)-partite graph. Our proof uses the recently developed theory of hypergraph containers, and a stability result for an extremal problem with two weighted colours. We also apply the stability method to obtain an exact Turán-type result for this extremal problem.
APA, Harvard, Vancouver, ISO, and other styles
39

Tenner, Bridget Eileen. "Boolean complexes and boolean numbers." Discrete Mathematics & Theoretical Computer Science DMTCS Proceedings vol. AN,..., Proceedings (2010). http://dx.doi.org/10.46298/dmtcs.2833.

Full text
Abstract:
International audience The Bruhat order gives a poset structure to any Coxeter group. The ideal of elements in this poset having boolean principal order ideals forms a simplicial poset. This simplicial poset defines the boolean complex for the group. In a Coxeter system of rank n, we show that the boolean complex is homotopy equivalent to a wedge of (n-1)-dimensional spheres. The number of these spheres is the boolean number, which can be computed inductively from the unlabeled Coxeter system, thus defining a graph invariant. For certain families of graphs, the boolean numbers have intriguing
APA, Harvard, Vancouver, ISO, and other styles
40

Guo, Jiyun, Haiyan Li, Yuqin Zhang, Lingling Liu, and Miao Fu. "On the existence of tripartite graphs and n-partite graphs." Open Mathematics 22, no. 1 (2024). https://doi.org/10.1515/math-2024-0093.

Full text
Abstract:
Abstract A sequence α \alpha of nonnegative integers is said to be graphic if it is the degree sequence of a simple graph G G , and such a graph G G is called a realization of α \alpha . In this article, we generalize Gale and Ryser’s theorem and give the sufficient condition and necessary condition for a triple to be realized by a tripartite graph. Not only that, we also give another stronger monotonous degree condition.
APA, Harvard, Vancouver, ISO, and other styles
41

Fischer, Eldar. "Induced Complete $h$-partite Graphs in Dense Clique-less Graphs." Electronic Journal of Combinatorics 6, no. 1 (1999). http://dx.doi.org/10.37236/1475.

Full text
Abstract:
It is proven that for every fixed $h$, $a$ and $b$, a graph with $n$ vertices and minimum degree at least ${h-1 \over h}n$, which contains no copy of $K_b$ (the complete graph with $b$ vertices), contains at least $(1-o(1)){n \over ha}$ vertex disjoint induced copies of the complete $h$-partite graph with $a$ vertices in each color class.
APA, Harvard, Vancouver, ISO, and other styles
42

Luan, Yu, Mei Lu, and Yi Zhang. "The fractional matching preclusion number of complete n-balanced k-partite graphs." Journal of Combinatorial Optimization, July 27, 2022. http://dx.doi.org/10.1007/s10878-022-00888-5.

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

Ni, Zhenyu, Jing Wang, and Liying Kang. "Spectral Extremal Graphs for Disjoint Cliques." Electronic Journal of Combinatorics 30, no. 1 (2023). http://dx.doi.org/10.37236/11516.

Full text
Abstract:
Let $kK_{r+1}$ be the graph consisting of $k$ vertex-disjoint copies of the complete graph $K_{r+1}$. Moon [Canad. J. Math. 20 (1968) 95--102] and Simonovits [Theory of Graphs (Proc. colloq., Tihany, 1996)] independently showed that if $n$ is sufficiently large, then the join of a complete graph $K_{k-1}$ and an $r$-partite Turán graph $T_{n-k+1,r}$ is the unique extremal graph for $kK_{r+1}$. In this paper we consider the graph which has the maximum spectral radius among all graphs without $k$ disjoint cliques. We show that if $G$ attains the maximum spectral radius over all $n$-vertex $kK_{r
APA, Harvard, Vancouver, ISO, and other styles
44

Geloun, Joseph Ben, and Sanjaye Ramgoolam. "Kronecker coefficients from algebras of bi-partite ribbon graphs." European Physical Journal Special Topics, May 26, 2023. http://dx.doi.org/10.1140/epjs/s11734-023-00850-4.

Full text
Abstract:
AbstractBi-partite ribbon graphs arise in organizing the large N expansion of correlators in random matrix models and in the enumeration of observables in random tensor models. There is an algebra $$\mathcal {K}(n)$$ K ( n ) , with basis given by bi-partite ribbon graphs with n edges, which is useful in the applications to matrix and tensor models. The algebra $$\mathcal {K}(n)$$ K ( n ) is closely related to symmetric group algebras and has a matrix-block decomposition related to Clebsch–Gordan multiplicities, also known as Kronecker coefficients, for symmetric group representations. Quantum
APA, Harvard, Vancouver, ISO, and other styles
45

Balbuena, Camino, P. García-Vázquez, Xavier Marcote, and J. C. Valenzuela. "Extremal K_(s,t)-free bipartite graphs." Discrete Mathematics & Theoretical Computer Science Vol. 10 no. 3, Graph and Algorithms (2008). http://dx.doi.org/10.46298/dmtcs.435.

Full text
Abstract:
Graphs and Algorithms International audience In this paper new exact values of the Zarankiewicz function z(m,n;s,t) are obtained assuming certain requirements on the parameters. Moreover, all the corresponding extremal graphs are characterized. Finally, an extension of this problem to 3-partite graphs is studied.
APA, Harvard, Vancouver, ISO, and other styles
46

Illingworth, Freddie. "The chromatic profile of locally colourable graphs." Combinatorics, Probability and Computing, May 10, 2022, 1–34. http://dx.doi.org/10.1017/s0963548322000050.

Full text
Abstract:
Abstract The classical Andrásfai-Erdős-Sós theorem considers the chromatic number of $K_{r + 1}$ -free graphs with large minimum degree, and in the case, $r = 2$ says that any n-vertex triangle-free graph with minimum degree greater than $2/5 \cdot n$ is bipartite. This began the study of the chromatic profile of triangle-free graphs: for each k, what minimum degree guarantees that a triangle-free graph is k-colourable? The chromatic profile has been extensively studied and was finally determined by Brandt and Thomassé. Triangle-free graphs are exactly those in which each neighbourhood is one-
APA, Harvard, Vancouver, ISO, and other styles
47

Illingworth, Freddie. "Minimum Degree Stability of H-Free Graphs." Combinatorica, May 12, 2023. http://dx.doi.org/10.1007/s00493-023-00010-1.

Full text
Abstract:
AbstractGiven an $$(r + 1)$$ ( r + 1 ) -chromatic graph H, the fundamental edge stability result of Erdős and Simonovits says that all n-vertex H-free graphs have at most $$(1 - 1/r + o(1)) \binom{n}{2}$$ ( 1 - 1 / r + o ( 1 ) ) n 2 edges, and any H-free graph with that many edges can be made r-partite by deleting $$o(n^{2})$$ o ( n 2 ) edges. Here we consider a natural variant of this—the minimum degree stability of H-free graphs. In particular, what is the least c such that any n-vertex H-free graph with minimum degree greater than cn can be made r-partite by deleting $$o(n^{2})$$ o ( n 2 )
APA, Harvard, Vancouver, ISO, and other styles
48

Xie, Chen, Hui Zhao, and Zhixi Wang. "Separability of Density Matrices of Graphs for Multipartite Systems." Electronic Journal of Combinatorics 20, no. 4 (2013). http://dx.doi.org/10.37236/3092.

Full text
Abstract:
We investigate separability of Laplacian matrices of graphs when seen as density matrices. This is a family of quantum states with many combinatorial properties. We firstly show that the well-known matrix realignment criterion can be used to test separability of this type of quantum states. The criterion can be interpreted as novel graph-theoretic idea. Then, we prove that the density matrix of the tensor product of N graphs is N-separable. However, the converse is not necessarily true. Additionally, we derive a sufficient condition for N-partite entanglement in star graphs and propose a neces
APA, Harvard, Vancouver, ISO, and other styles
49

Gerbner, Dániel. "Some Exact Results for Non-Degenerate Generalized Turán Problems." Electronic Journal of Combinatorics 30, no. 4 (2023). http://dx.doi.org/10.37236/11574.

Full text
Abstract:
The generalized Turán number $\mathrm{ex}(n,H,F)$ is the maximum number of copies of $H$ in $n$-vertex $F$-free graphs. We consider the case where $\chi(H)<\chi(F)$. There are several exact results on $\mathrm{ex}(n,H,F)$ when the extremal graph is a complete $(\chi(F)-1)$-partite graph. We obtain multiple exact results with other kinds of extremal graphs.
APA, Harvard, Vancouver, ISO, and other styles
50

Conlon, David, Joonkyung Lee, and Alexander Sidorenko. "Extremal Numbers and Sidorenko’s Conjecture." International Mathematics Research Notices, April 24, 2024. http://dx.doi.org/10.1093/imrn/rnae071.

Full text
Abstract:
Abstract Sidorenko’s conjecture states that, for all bipartite graphs $H$, quasirandom graphs contain asymptotically the minimum number of copies of $H$ taken over all graphs with the same order and edge density. While still open for graphs, the analogous statement is known to be false for hypergraphs. We show that there is some advantage in this, in that if Sidorenko’s conjecture does not hold for a particular $r$-partite $r$-uniform hypergraph $H$, then it is possible to improve the standard lower bound, coming from the probabilistic deletion method, for its extremal number $\textrm {ex}(n,H
APA, Harvard, Vancouver, ISO, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography