Relevant bibliographies by topics / Cycle graph C_n / Journal articles

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

Journal articles on the topic 'Cycle graph C_n'

Author: Grafiati

Published: 7 June 2025

Last updated: 9 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 'Cycle graph C_n.'

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.

Mn, Abdilla Nurul Azisah, Hasmawati Hasmawati, and Budi Nurwahyu. "Edge Metric Dimension of Comb Product Cycles Versus Stars and Fans." Journal of Advanced Research in Applied Sciences and Engineering Technology 49, no. 2 (2024): 52–63. http://dx.doi.org/10.37934/araset.49.2.5263.

Full text

Abstract:

The edge metric dimension finding of a graph resulting from the comb product on a cycle graph to the complete graph and the fact about the dominant vertex in the complete graph arise a problem about the edge metric dimension of a graph resulting from the comb product on a cycle graph to the other graphs that have dominant vertex such as star and fan graph. This study aims to determine the edge metric dimension of the graph resulting from the comb product on a cycle graph to the star and fan graph, respectively. The results show that the upper and lower bound of the edge metric dimension of both graphs are equivalent so that an exact edge metric dimension is obtained. The edge metric dimension of the graph comb product of the cycle graph C_n to the star graph S_(1,m) is n(m-1). The edge metric dimension of the graph comb product of the cycle graph C_n to the fan graph F_(1,m) is n(m-1).

APA, Harvard, Vancouver, ISO, and other styles

Grzelec, Igor, Tom� Madaras, and Alfr�d Onderko. "On uniqueness of packing of three copies of 2-factors." Opuscula Mathematica 45, no. 1 (2025): 79–101. https://doi.org/10.7494/opmath.2025.45.1.79.

Full text

Abstract:

The packing of three copies of a graph $G$ is the union of three edge-disjoint copies (with the same vertex set) of $G$. In this paper, we completely solve the problem of the uniqueness of packing of three copies of 2-regular graphs. In particular, we show that $C_3,C_4,C_5,C_6$ and $2C_3$ have no packing of three copies, $C_7,C_8,C_3 \cup C_4, C_4 \cup C_4, C_3 \cup C_5$ and $3C_3$ have unique packing, and any other collection of cycles has at least two distinct packings.

APA, Harvard, Vancouver, ISO, and other styles

G, Vembarasi, and Gowri R. "Super Root Cube of Cube Difference Labeling of Some Special Graphs." Indian Journal of Science and Technology 14, no. 35 (2021): 2778–83. https://doi.org/10.17485/IJST/v14i35.1336.

Full text

Abstract:

Abstract Background/Objectives: This study gives an extended and the new kinds of super root cube of cube difference labeling of some graphs are obtained. Methods/ Findings: We derive super root cube of cube difference labeling of path related graph and analyzed cycle related graphs. Keywords: Triangular Snake T_n; Cycle graph C_n; Crown C_n©K_1; pendent edge to both sides of each vertex of a path Pn; supr root cube of cube difference labeling of graphs.

APA, Harvard, Vancouver, ISO, and other styles

Paluga, Rolando N. "Monophonic Polynomial of the Join of Graphs." Journal of the Indonesian Mathematical Society 31, no. 1 (2025): 1686. https://doi.org/10.22342/jims.v31i1.1686.

Full text

Abstract:

The monophonic polynomial of a graph $G$, denoted by $M(G,x)$, is the polynomial $M(G,x) = \sum_{k=m(G)}^{|G|}M(G, k)x^k $, where $|G|$ is the order of $G$ and $M(G, k)$ is the number of monophonic sets in $G$ with cardinality $k$. In this paper, we delve into some characterizations of monophonic sets in the join of two graphs and use it to determine its corresponding monophonic polynomial. Moreover, we also present the monophonic polynomials of the complete graph $K_n$ $(n \geq 1)$, the path $P_n$ $(n \geq 3)$, the cycle $C_n$ $(n \geq 4)$, the fan $F_n$ $(n \geq 3)$, the wheel $W_n$ $(n \geq 4)$, the complete bipartite $K_{m,n}$ $(m, n \geq 1)$, $P_m + P_n$ ($m, n \geq 3$), $C_m + C_n$ ($m, n \geq 4$), $P_m + C_n$ ($m \geq 3$ and $n \geq 4$), $P_m + \overline{K_n}$ ($m \geq 3$ and $n \geq 2$), and $C_m + \overline{K_n}$ ($m \geq 4$ and $n \geq 2$). In general, we obtain the monophonic polynomial of the join of two graphs.

APA, Harvard, Vancouver, ISO, and other styles

Javadi, R., F. Khoeini, G. R. Omidi, and A. Pokrovskiy. "On the Size-Ramsey Number of Cycles." Combinatorics, Probability and Computing 28, no. 06 (2019): 871–80. http://dx.doi.org/10.1017/s0963548319000221.

Full text

Abstract:

AbstractFor given graphs G1,…, Gk, the size-Ramsey number $\hat R({G_1}, \ldots ,{G_k})$ is the smallest integer m for which there exists a graph H on m edges such that in every k-edge colouring of H with colours 1,…,k, H contains a monochromatic copy of Gi of colour i for some 1 ≤ i ≤ k. We denote $\hat R({G_1}, \ldots ,{G_k})$ by ${\hat R_k}(G)$ when G1 = ⋯ = Gk = G.Haxell, Kohayakawa and Łuczak showed that the size-Ramsey number of a cycle Cn is linear in n, ${\hat R_k}({C_n}) \le {c_k}n$ for some constant ck. Their proof, however, is based on Szemerédi’s regularity lemma so no specific constant ck is known.In this paper, we give various upper bounds for the size-Ramsey numbers of cycles. We provide an alternative proof of ${\hat R_k}({C_n}) \le {c_k}n$ , avoiding use of the regularity lemma, where ck is exponential and doubly exponential in k, when n is even and odd, respectively. In particular, we show that for sufficiently large n we have ${\hat R_2}({C_n}) \le {10^5} \times cn$ , where c = 6.5 if n is even and c = 1989 otherwise.

APA, Harvard, Vancouver, ISO, and other styles

Wang, Haiying, Muhammad Javaid, Sana Akram, Muhammad Jamal, and Shaohui Wang. "Least eigenvalue of the connected graphs whose complements are cacti." Open Mathematics 17, no. 1 (2019): 1319–31. http://dx.doi.org/10.1515/math-2019-0097.

Full text

Abstract:

Abstract Suppose that Γ is a graph of order n and A(Γ) = [ai,j] is its adjacency matrix such that ai,j is equal to 1 if vi is adjacent to vj and ai,j is zero otherwise, where 1 ≤ i, j ≤ n. In a family of graphs, a graph is called minimizing if the least eigenvalue of its adjacency matrix is minimum in the set of the least eigenvalues of all the graphs. Petrović et al. [On the least eigenvalue of cacti, Linear Algebra Appl., 2011, 435, 2357-2364] characterized a minimizing graph in the family of all cacti such that the complement of this minimizing graph is disconnected. In this paper, we characterize the minimizing graphs G ∈ $\begin{array}{} {\it\Omega}^c_n \end{array}$, i.e. $$\begin{array}{} \displaystyle \lambda_{min}(G)\leq\lambda_{min}(C^c) \end{array}$$ for each Cc ∈ $\begin{array}{} {\it\Omega}^c_n \end{array}$, where $\begin{array}{} {\it\Omega}^c_n \end{array}$ is a collection of connected graphs such that the complement of each graph of order n is a cactus with the condition that either its each block is only an edge or it has at least one block which is an edge and at least one block which is a cycle.

APA, Harvard, Vancouver, ISO, and other styles

Drury, Stephen, and Huiqiu Lin. "Some Graphs Determined By Their Distance Spectrum." Electronic Journal of Linear Algebra 34 (February 21, 2018): 320–30. http://dx.doi.org/10.13001/1081-3810.3613.

Full text

Abstract:

Let $G$ be a connected graph with order $n$. Let $\lambda_1(D(G))\geq \cdots\geq \lambda_n(D(G))$ be the distance spectrum of $G$. In this paper, it is shown that the complements of $P_n$ and $C_n$ are determined by their $D$-spectrum. Moreover, it is shown that the cycle $C_n$ ($n$ odd) is also determined by its $D$-spectrum.

APA, Harvard, Vancouver, ISO, and other styles

Bonifacio, Jhon Cris, Clarence Joy Andaya, and Daryl Magpantay. "On the j-Edge Intersection Graph of Cycle Graph." European Journal of Pure and Applied Mathematics 16, no. 4 (2023): 2476–98. http://dx.doi.org/10.29020/nybg.ejpam.v16i4.4870.

Full text

Abstract:

This paper defines a new class of graphs using the spanning subgraphs of a cycle graph as vertices. This class of graphs is called $j$-edge intersection graph of cycle graph, denoted by $E_{C_{(n,j)}}$. The vertex set of $E_{C_{(n,j)}}$ is the set of spanning subgraphs of cycle graph with $j$ edges where $n \geq 3$ and $j$ is a nonnegative integer such that $1 \leq j \leq n$. Moreover, two distinct vertices are adjacent if they have exactly one edge in common. $E_{C_{(n,j)}}$ is considered as a simple graph. Furthermore, $E_{C_{(n,j)}}$ is characterized by the value of $j$ that is when $j=1$ or $\lceil \frac{n}{2} \rceil < j \leq n$ and $2 \leq j \leq \lceil \frac{n}{2} \rceil$. When $j=1$ or $\lceil \frac{n}{2} \rceil < j \leq n$, the new graph only produced an empty graph. Hence, the proponents only considered the value when $2 \leq j \leq \lceil \frac{n}{2} \rceil$ in determining the order and size of $E_{C_{(n,j)}}$. Moreover, this paper discusses necessary and sufficient conditions where the $j$-edge intersection graph of $C_n$ is isomorphic to the cycle graph. Furthermore, the researchers determined a lower bound for the independence number, and an upper bound for the domination number of $E_{C_{(n,j)}}$ when $j=2$.

APA, Harvard, Vancouver, ISO, and other styles

Dewi, Putu Kartika. "The Modular Irregularity Strength of C_n⊙mK_1." InPrime: Indonesian Journal of Pure and Applied Mathematics 4, no. 2 (2022): 160–69. http://dx.doi.org/10.15408/inprime.v4i2.26935.

Full text

Abstract:

Let G(V, E) be a graph with order n with no component of order 2. An edge k-labeling α: E(G) →{1,2,…,k} is called a modular irregular k-labeling of graph G if the corresponding modular weight function wt_ α:V(G) → Z_n defined by wt_ α(x) =Ʃ_(xyϵE(G)) α(xy) is bijective. The value wt_α(x) is called the modular weight of vertex x. Minimum k such that G has a modular irregular k-labeling is called the modular irregularity strength of graph G. In this paper, we define a modular irregular labeling on C_n⊙mK_1. Furthermore, we determine the modular irregularity strength of C_n⊙mK_1.Keywords: corona product; cycle; empty graph; modular irregular labeling; modular irregularity strength. AbstrakDiberikan graf G(V, E) dengan orde n dengan tidak ada komponen yang berorde 2. Sebuah pelabelan-k sisi α: E(G) →{1,2,…,k} disebut pelabelan-k tak teratur modular pada graf G jika fungsi bobot modularnya wt_ α:V(G) → Z_n dengan wt_ α(x) =Ʃ_(xyϵE(G)) α(xy) merupakan fungsi bijektif. Nilai wt_α(x) disebut bobot modular dari simpul x. Minimum dari k sehingga G mempunyai pelabelan-k tak teratur modular disebut dengan kekuatan ketakteraturan modular dari graf G. Pada tulisan ini, didefinisikan pelabelan tak teratur modular pada C_n⊙mK_1. Lebih lanjut, ditentukan kekuatan ketakteraturan modular dari C_n⊙mK_1.Kata Kunci: hasil kali korona; lingkaran, graf kosong; pelabelan tak teratur modular; kekuatan ketakteraturan modular.

APA, Harvard, Vancouver, ISO, and other styles

Suparta, I. Nengah, Mathiyazhagan Venkatachalam, I. Gede Aris Gunadi, and Putu Andi Cipta Pratama. "GRACEFUL CHROMATIC NUMBER OF SOME CARTESIAN PRODUCT GRAPHS." Ural Mathematical Journal 9, no. 2 (2023): 193. http://dx.doi.org/10.15826/umj.2023.2.016.

Full text

Abstract:

A graph $G(V,E)$ is a system consisting of a finite non empty set of vertices $V(G)$ and a set of edges $E(G)$. A (proper) vertex colouring of $G$ is a function $f:V(G)\rightarrow \{1,2,\ldots,k\},$ for some positive integer $k$ such that $f(u)\neq f(v)$ for every edge $uv\in E(G)$. Moreover, if $|f(u)-f(v)|\neq |f(v)-f(w)|$ for every adjacent edges $uv,vw\in E(G)$, then the function $f$ is called graceful colouring for $G$. The minimum number $k$ such that $f$ is a graceful colouring for $G$ is called the graceful chromatic number of $G$. The purpose of this research is to determine graceful chromatic number of Cartesian product graphs $C_m \times P_n$ for integers $m\geq 3$ and $n\geq 2$, and $C_m \times C_n$ for integers $m,n\geq 3$. Here, $C_m$ and $P_m$ are cycle and path with $m$ vertices, respectively. We found some exact values and bounds for graceful chromatic number of these mentioned Cartesian product graphs.

APA, Harvard, Vancouver, ISO, and other styles

Barack, Zeveliano Zidane, and Kiki Ariyanti Sugeng. "Modular irregularity strength of disjoint union of cycle-related graph." ITM Web of Conferences 61 (2024): 01001. http://dx.doi.org/10.1051/itmconf/20246101001.

Full text

Abstract:

Let G = (V,E) be a graph with a vertex set V and an edge set E of G, with order n. Modular irregular labeling of a graph G is an edge k-labeling φ:E → {1, 2,…,k} such that the modular weight of all vertices is all different. The modular weight is defined by wtφ(u) = Σv∈N(u) φ(uv) (mod n). The minimum number k such that a graph G has modular irregular labeling with the largest label k is called modular irregularity strength of G. In this research, we determine the modular irregularity strength for a disjoint union of cycle graph, $ (mC_{n})=\frac{mn}{2}+1 $ for n ≡ 0 (mod 4), a disjoint union of sun graph, ms(m(Cn ⊙ K1))2 = ∞ for n and m even and ms(m(Cn ⊙ K1)) = mn otherwise, and a disjoint union of middle graph of cycle graph, ms(mM(Cn)) = ∞ for n and m both odd numbers and $(mM({C_n})) = {{mn} \over 2} + 1$ otherwise.

APA, Harvard, Vancouver, ISO, and other styles

Kajiwara, Takeshi, Norio Konno, Shohei Koyama, and Kei Saito. "Periodicity for the 3-state quantum walk on cycles." quantum Information and Computation 19, no. 13&14 (2019): 1081–88. http://dx.doi.org/10.26421/qic19.13-14-1.

Full text

Abstract:

Dukes (2014) and Konno, Shimizu, and Takei (2017) studied the periodicity for 2-state quantum walks whose coin operator is the Hadamard matrix on cycle graph C_N with N vertices. The present paper treats the periodicity for 3-state quantum walks on C_N. Our results follow from a new method based on the cyclotomic field. This method gives a necessary condition for the coin operator for quantum walks to be periodic. Moreover, we reveal the period T_N of typical two kinds of quantum walks, the Grover and Fourier walks. We prove that both walks do not have any finite period except for N=3, in which case T_3=6 (Grover), =12 (Fourier).

APA, Harvard, Vancouver, ISO, and other styles

Staš, Michal, and Juraj Valiska. "On the crossing numbers of join products of W_{4}+P_{n} and W_{4}+C_{n}." Opuscula Mathematica 41, no. 1 (2021): 95–112. http://dx.doi.org/10.7494/opmath.2021.41.1.95.

Full text

Abstract:

The crossing number $\mathrm{cr}(G)$ of a graph $G$ is the minimum number of edge crossings over all drawings of $G$ in the plane. The main aim of the paper is to give the crossing number of the join product $W_4+P_n$ and $W_4+C_n$ for the wheel $W_4$ on five vertices, where $P_n$ and $C_n$ are the path and the cycle on $n$ vertices, respectively. Yue et al. conjectured that the crossing number of $W_m+C_n$ is equal to $Z(m+1)Z(n)+(Z(m)-1) \big \lfloor \frac{n}{2} \big \rfloor + n+ \big\lceil\frac{m}{2}\big\rceil +2$, for all $m,n \geq 3$, and where the Zarankiewicz's number $Z(n)=\big \lfloor \frac{n}{2} \big \rfloor \big \lfloor \frac{n-1}{2} \big \rfloor$ is defined for $n\geq 1$. Recently, this conjecture was proved for $W_3+C_n$ by Klešč. We establish the validity of this conjecture for $W_4+C_n$ and we also offer a new conjecture for the crossing number of the join product $W_m+P_n$ for $m\geq 3$ and $n\geq 2$.

APA, Harvard, Vancouver, ISO, and other styles

SREETHU, K., and SEEMA VARGHESE. "Power Domination in Generalized Mycielskian of Cycles." Creative Mathematics and Informatics 33, no. 2 (2024): 289–95. http://dx.doi.org/10.37193/cmi.2024.02.14.

Full text

Abstract:

Let $ G=G(V,E) $ be a graph. A set $ S\subseteq V $ is a power dominating set of $ G $ if $ S $ observes all the vertices in $ V,$ following two rules: domination and propagation. The cardinality of a minimum power dominating set is called the power domination number. In this paper, we compute the power domination number of generalized $ m $-Mycielskian of a cycle, $ C_n $. We found that it depends on the numbers $ n \an m $.

APA, Harvard, Vancouver, ISO, and other styles

R.N. Rajalekshmi and R. Kala. "Group mean cordial labeling of some splitting graphs." Malaya Journal of Matematik 8, no. 04 (2020): 2352–55. http://dx.doi.org/10.26637/mjm0804/0181.

Full text

Abstract:

Let $G$ be a $(p, q)$ graph and let $A$ be a group. Let $f: V(G) \longrightarrow A$ be a map. For each edge $u v$ assign the label $\left\lfloor\frac{o(f(u))+o(f(v))}{2} \mid\right.$. Here $o(f(u))$ denotes the order of $f(u)$ as an element of the group $A$. Let $\mathbb{I}$ be the set of all integers that are labels of the edges of $G$. $f$ is called a group mean cordial labeling if the following conditions hold:(1) For $x, y \in A,\left|v_f(x)-v_f(y)\right| \leq 1$, where $v_f(x)$ is the number of vertices labeled with $x$.(2) For $i, j \in \mathbb{I},\left|e_f(i)-e_f(j)\right| \leq 1$, where $e_f(i)$ denote the number of edges labeled with $i$.A graph with a group mean cordial labeling is called a group mean cordial graph. In this paper, we take $A$ as the group of fourth roots of unity and prove that,the splitting graphs of Path $\left(P_n\right), \operatorname{Cycle}\left(C_n\right), \operatorname{Comb}\left(P_n \odot K_1\right)$ and Complete Bipartite graph ( $K_{n, n}$ when $n$ is even ) are group mean cordial graphs. Also we characterized the group mean cordial labeling of the splitting graph of $K_{1, n}$.

APA, Harvard, Vancouver, ISO, and other styles

Hildebrand, Roland. "Extremal Copositive Matrices with Zero Supports of Cardinality n-2." Electronic Journal of Linear Algebra 34 (February 21, 2018): 28–34. http://dx.doi.org/10.13001/1081-3810.3649.

Full text

Abstract:

Let $A \in {\cal C}^n$ be an exceptional extremal copositive $n \times n$ matrix with positive diagonal. A zero $u$ of $A$ is a non-zero nonnegative vector such that $u^TAu = 0$. The support of a zero $u$ is the index set of the positive elements of $u$. A zero $u$ is minimal if there is no other zero $v$ such that $\Supp v \subset \Supp u$ strictly. Let $G$ be the graph on $n$ vertices which has an edge $(i,j)$ if and only if $A$ has a zero with support $\{1,\dots,n\} \setminus \{i,j\}$. In this paper, it is shown that $G$ cannot contain a cycle of length strictly smaller than $n$. As a consequence, if all minimal zeros of $A$ have support of cardinality $n - 2$, then $G$ must be the cycle graph $C_n$.

APA, Harvard, Vancouver, ISO, and other styles

Odyuo, Aronthung S., and P. Mercy. "On Fibonacci Range Labeling for Standard Shell Graphs." Journal of Advances in Mathematics and Computer Science 38, no. 7 (2023): 67–75. http://dx.doi.org/10.9734/jamcs/2023/v38i71773.

Full text

Abstract:

A shell C[n, (n - 3)] of size n is a graph obtained by taking (n - 3) concurrent chords in a cycle $C_n$ on n vertices. Deb and Limaye (2002) have conjectured that all multiple shells are harmonious. The conjecture has prove to be true for uniform double shells, uniform triple shells and uniform quadruple shells. Here, we prove for a non- uniform double shells with order m and n, where n = (m - 1) and $\kappa$-copies of a shell C[n, (n - 3)]$\kappa$ with a union of $K_2$ for n = 4, 2$K_2$ for n = 6 and 3$K_2$ for n = 8, having a common end vertex joined to the apex of the shell are Fibonacci range labeling.

APA, Harvard, Vancouver, ISO, and other styles

Xu, Lee. "A Study of the Eigenvalues of the Matrix Of Distance Reciprocals in K[r, n-r] And The Cycle C_n." Galoitica: Journal of Mathematical Structures and Applications 6, no. 2 (2023): 08–16. http://dx.doi.org/10.54216/gjmsa.060201.

Full text

Abstract:

This paper Deals with the complete bipartite graph K(r, n-r) and the cycle . The matrix of concern is the matrix B which is the (n, n) matrix and whose non zero entries are the reciprocals of the non zero entries of the distance matrix D. A complete characterization of the spectrum of B and a set of n independent eigenvectors of B will be presented. Two special cases will be mentioned, namely the star K(1, n-1) and the graph K(2, n-2). We will also look at the case of infinite graph, i. e if the size n grows big while r stays finite. Finally, some numerical data will be presented. As for the cycle, we present the complete set of eigenvalues of the matrix B.

APA, Harvard, Vancouver, ISO, and other styles

Öner, Tarkan, and Erdi Ateş. "Investigation of $C_m$-Supermagic Properties in the Union of $C_n$ and $C_m$ Graph Structures." Journal of New Theory, no. 50 (March 28, 2025): 9–29. https://doi.org/10.53570/jnt.1626094.

Full text

Abstract:

Graph labeling, the assignment of numbers to the vertices or edges of a graph, finds applications in diverse fields such as network addressing, channel allocation, data mining, image processing, cryptography, and logistics. A $C_m$-supermagic labeling involves assigning integers to a graph's edges and vertices such that the labels' sum for all $C_m$ cycles equals a constant value. This paper explores the $C_m$-supermagic properties of the $Cl_{n,m}$ graph, formed by the union of a $C_n$ graph and $n$ $C_m$ graphs. It comprehensively analyzes the conditions under which $Cl_{n,m}$ exhibits $C_m$-supermagic properties and derive explicit labeling constructions. These results contribute to understanding $C_m$-supermagic graphs and their potential applications in theoretical and applied domains.

APA, Harvard, Vancouver, ISO, and other styles

FU, CHIN-MEI, and WEN-CHUNG HUANG. "DECOMPOSITIONS OF $K_{m,n}$ INTO 4-CYCLES AND 8-CYCLES." Tamkang Journal of Mathematics 29, no. 1 (1998): 69–72. http://dx.doi.org/10.5556/j.tkjm.29.1998.4302.

Full text

Abstract:

In this paper it is shown that $G$ can be decomposed into $p$ copies of $C_4$ and $q$ copies of $C_8$ for each pair of nonnegative integers $p$ and $q$ which 8atisfics the equation $4p+ Sq = |E(G)|$, where $E(G)$ is the number of_edges of $G$, when (1) $G = K_{m, n}$ the complete bigartite graph, if $m$ and $n$ are even, (2) $G = K_{m, n}-F$, $K_{m, n}$ with 1-factor removed, if $m = n \equiv 1$ (mod 4), and (3) $G = K_{m, n}-(F \cup C_6)$, $K_{m, n}$,with 1-factor and one 6-cycle removed, if $m = n \equiv 3$ (mod 4).

APA, Harvard, Vancouver, ISO, and other styles

Akwu, Abolape Deborah, and Opeyemi Oyewumi. "$C_{6}$-decompositions of the tensor product of complete graphs." Open Journal of Discrete Applied Mathematics 3, no. 3 (2020): 62–65. http://dx.doi.org/10.30538/psrp-odam2020.0044.

Full text

Abstract:

Let $G$ be a simple and finite graph. A graph is said to be decomposed into subgraphs $H_1$ and $H_2$ which is denoted by $G= H_1 \oplus H_2$, if $G$ is the edge disjoint union of $H_1$ and $H_2$. If $G= H_1 \oplus H_2 \oplus \cdots \oplus H_k$, where $H_1$, $H_2$, ..., $H_k$ are all isomorphic to $H$, then $G$ is said to be $H$-decomposable. Furthermore, if $H$ is a cycle of length $m$ then we say that $G$ is $C_m$-decomposable and this can be written as $C_m|G$. Where $ G\times H$ denotes the tensor product of graphs $G$ and $H$, in this paper, we prove that the necessary conditions for the existence of $C_6$-decomposition of $K_m \times K_n$ are sufficient. Using these conditions it can be shown that every even regular complete multipartite graph $G$ is $C_6$-decomposable if the number of edges of $G$ is divisible by $6$.

APA, Harvard, Vancouver, ISO, and other styles

Wang, Xingxing, Mengjie Li, Wenxue Shi, Yue Wu, and Yuting Zhao. "Improvement of Sufficient Conditions for Pancyclic Graphs." Scientific Journal of Technology 6, no. 1 (2024): 29–32. http://dx.doi.org/10.54691/w10e3408.

Full text

Abstract:

The study of cyclic graphs has always been a hot topic in the field of graph theory and has received widespread attention from graph theory practitioners. If an n-order graph G exactly contains cycles of all lengths from 3 to n, then the graph is called a pan cycle graph. This article proves that, after excluding some special cases, when the number of edges in graph G is greater than or equal to C2n-3+12, graph G must be a pan cyclic graph.

APA, Harvard, Vancouver, ISO, and other styles

Barr, Katharine E., Tim J. Proctor, Daniel Allen, and Viv M. Kendon. "Periodicity and perfect state transfer in quantum walks on variants of cycles." Quantum Information and Computation 14, no. 5&6 (2014): 417–38. http://dx.doi.org/10.26421/qic14.5-6-3.

Full text

Abstract:

We systematically investigated perfect state transfer between antipodal nodes of discrete time quantum walks on variants of the cycles $C_4$, $C_6$ and $C_8$ for three choices of coin operator. Perfect state transfer was found, in general, to be very rare, only being preserved for a very small number of ways of modifying the cycles. We observed that some of our useful modifications of $C_4$ could be generalised to an arbitrary number of nodes, and present three families of graphs which admit quantum walks with interesting dynamics either in the continuous time walk, or in the discrete time walk for appropriate selections of coin and initial conditions. These dynamics are either periodicity, perfect state transfer, or very high fidelity state transfer. These families are modifications of families known not to exhibit periodicity or perfect state transfer in general. The robustness of the dynamics is tested by varying the initial state, interpolating between structures and by adding decoherence.

APA, Harvard, Vancouver, ISO, and other styles

Fernández, Irene, Jaehoon Kim, Younjin Kim, and Hong Liu. "Nested cycles with no geometric crossings." Proceedings of the American Mathematical Society, Series B 9, no. 3 (2022): 22–32. http://dx.doi.org/10.1090/bproc/107.

Full text

Abstract:

In 1975, Erdős asked the following question: what is the smallest function f ( n ) f(n) for which all graphs with n n vertices and f ( n ) f(n) edges contain two edge-disjoint cycles C 1 C_1 and C 2 C_2 , such that the vertex set of C 2 C_2 is a subset of the vertex set of C 1 C_1 and their cyclic orderings of the vertices respect each other? We prove the optimal linear bound f ( n ) = O ( n ) f(n)=O(n) using sublinear expanders.

APA, Harvard, Vancouver, ISO, and other styles

Arathi Bhat, K., and G. Sudhakara. "Powers of cycle graph which are k-self complementary and k-co-self complementary." Proyecciones (Antofagasta) 41, no. 3 (2022): 715–32. http://dx.doi.org/10.22199/issn.0717-6279-4638.

Full text

Abstract:

E. Sampath Kumar and L. Pushpalatha [4] introduced a generalized version of complement of a graph with respect to a given partition of its vertex set. Let G = (V,E) be a graph and P = {V₁, V₂,...,Vk} be a partition of V of order k ≥ 1. The k-complement GPk of G with respect to P is defined as follows: For all Vi and Vj in P, i ≠ j, remove the edges between Vi and Vj , and add the edges which are not in G. Analogues to self complementary graphs, a graph G is k-self complementary (k-s.c.) if GPk ≅ G and is k-co-self complementary (k-co.s.c.) if GPk ≅ Ġ with respect to a partition P of V (G). The mth power of an undirected graph G, denoted by Gm is another graph that has the same set of vertices as that of G, but in which two vertices are adjacent when their distance in G is at most m. In this article, we study powers of cycle graphs which are k-self complementary and k-co-self complementary with respect to a partition P of its vertex set and derive some interesting results. Also, we characterize k-self complementary C2n and the respective partition P of V (C2n). Finally, we prove that none of the C2n is k-co-self complementary for any partition P of V (C2n).

APA, Harvard, Vancouver, ISO, and other styles

Sutjijana, Aluysius, and Dea Alvionita Azka. "ANTIADJACENCY MATRICES FOR SOME STRONG PRODUCTS OF GRAPHS." Journal of Fundamental Mathematics and Applications (JFMA) 6, no. 1 (2023): 27–36. http://dx.doi.org/10.14710/jfma.v6i1.16653.

Full text

Abstract:

Let G be an undirected graphs with no multiple edges. There are many ways to represent a graph, and one of them is in a matrix form, by constructing an antiadjacency matrix. Given a connected graph G with vertex set $V$ consisting of n members, an antiadjacency matrix of the graph G is a matrix B of order n \times n such that if there is an edge that connects vertex v_i to vertex v_j (v_i \sim v_j ) then the element of i^{th} row and b^{th} column of B is 0, otherwise 1. In this paper we investigate some properties of antiadjacency matrices for some strong product of two graphs. Our results are general forms of the antiadjacency matrix of the strong product of path graphs P_m with P_n for m, n\ge 3, and cycle graphs C_m with C_m for m \ge 3.

APA, Harvard, Vancouver, ISO, and other styles

Ezhilarasi, A. Pauline, and A. Muthusamy. "Decomposition of the cartesian product of complete graphs into paths and cycles of length six." Journal of Combinatorial Mathematics and Combinatorial Computing 124 (March 19, 2025): 581–600. https://doi.org/10.61091/jcmcc124-39.

Full text

Abstract:

Let $P_k$ and $C_k$ respectively denote a path and a cycle on $k$ vertices. In this paper, we give necessary and sufficient conditions for the existence of a complete $\left\{P_7,C_6\right\}$-decomposition of the cartesian product of complete graphs.

APA, Harvard, Vancouver, ISO, and other styles

Saputra, Nur Wigi, Siti Khabibah, Lucia Ratnasari, and Robertus Heri Soelistyo Utomo. "Integer Cordial Labelling on Graphs nF_(m_i ) (n-1) P_t With m_i Even or Odd." Journal of Mathematics Research 16, no. 6 (2025): 29. https://doi.org/10.5539/jmr.v16n6p29.

Full text

Abstract:

This paper discusses the integer cordial labeling on the graph nF_(m_i)(n-1)P_t when m_i is even or odd. The graph nF_m(n-1)P_t is obtained from n friendship graphs connected by n-1 paths P_t at vertices other than the central vertex of the graph for the i-th and i+1-th graphs where 1&le;i&le;n. Additionally, m_i denotes the number of copies of the cycle C_3 for each friendship graph. The main result is the integer cordial label for this graph. Furthermore, it was proved that nF_m(n-1)P_t when m_i even or odd is a graph with integer cordial labeling.

APA, Harvard, Vancouver, ISO, and other styles

Zhou, Yun-Xia, and Hong-Hai Li. "On the tricyclic graphs with three disjoint 6-cycles and maximum matching energy." Tamkang Journal of Mathematics 46, no. 4 (2015): 389–99. http://dx.doi.org/10.5556/j.tkjm.46.2015.1768.

Full text

Abstract:

The matching energy of a graph was introduced recently by Gutman and Wagner and defined as the sum of the absolute values of zeros of its matching polynomial. In this paper, we characterize graphs that attain the maximum matching energy among all connected tricyclic graphs of order $n$ with three vertex-disjoint $C_6$'s.

APA, Harvard, Vancouver, ISO, and other styles

LIU, Hongxia, and Xiaogang PAN. "On perfect 2-matching uniform graphs." Proceedings of the Romanian Academy, Series A: Mathematics, Physics, Technical Sciences, Information Science 25, no. 2 (2024): 95–102. http://dx.doi.org/10.59277/pra-ser.a.25.2.02.

Full text

Abstract:

Let $G$ be a graph. For a set $\mathcal{H}$ of connected graphs, an $\mathcal{H}$-factor of graph $G$ is a spanning subgraph $H$ of $G$ such that every component of $H$ is isomorphic to a member of $\mathcal{H}$. Denote $\mathcal{H}=\{P_2\}\cup \{C_i|i\ge 3\}$. We call $\mathcal{H}$-factor a perfect 2-matching of $G$, that is, a perfect 2-matching is a spanning subgraph of $G$ such that each component of $G$ is either an edge or a cycle. In this paper, we define the new concept of perfect $2$-matching uniform graph, namely, a graph $G$ is called a perfect $2$-matching uniform graph if for arbitrary two distinct edges $e_1$ and $e_2$ of $G$, $G$ contains a perfect $2$-matching containing $e_1$ and avoiding $e_2$. In addition, we study the relationship between some graphic parameters and the existence of perfect $2$-matching uniform graphs. The results obtained in this paper are sharp in some sense.

APA, Harvard, Vancouver, ISO, and other styles

R. Keerthana and S. Venkatesh. "On fuzzy labeling of cycle with k-parallel P_s and C_s chords." Multidisciplinary Science Journal 6 (December 15, 2023): 2024ss0111. http://dx.doi.org/10.31893/multiscience.2024ss0111.

Full text

Abstract:

Fuzzy Labeling is one of the emerging areas in fuzzy graph theory. In this article, fuzzy labeling of cycle with chord related graphs like cycle with parallel chord, cycle with -parallel chord, cycle with -parallel chord are investigated.

APA, Harvard, Vancouver, ISO, and other styles

Yahya, Nisky Imansyah, Ainun Fatmawati, Nurwan Nurwan, and Salmun K. Nasib. "RAINBOW VERTEX-CONNECTION NUMBER ON COMB PRODUCT OPERATION OF CYCLE GRAPH (C_4) AND COMPLETE BIPARTITE GRAPH (K_(3,N))." BAREKENG: Jurnal Ilmu Matematika dan Terapan 17, no. 2 (2023): 0673–84. http://dx.doi.org/10.30598/barekengvol17iss2pp0673-0684.

Full text

Abstract:

Rainbow vertex-connection number is the minimum colors assignment to the vertices of the graph, such that each vertex is connected by a path whose edges have distinct colors and is denoted by . The rainbow vertex connection number can be applied to graphs resulting from operations. One of the methods to create a new graph is to perform operations between two graphs. Thus, this research uses comb product operation to determine rainbow-vertex connection number resulting from comb product operation of cycle graph and complete bipartite graph & . The research finding obtains the theorem of rainbow vertex-connection number at the graph of for while the theorem of rainbow vertex-connection number at the graph of for for .

APA, Harvard, Vancouver, ISO, and other styles

Lourdusamy, A., and T. Mathivanan. "Herscovici’s conjecture on C2n × G." Discrete Mathematics, Algorithms and Applications 12, no. 05 (2020): 2050071. http://dx.doi.org/10.1142/s1793830920500718.

Full text

Abstract:

The [Formula: see text]-pebbling number, [Formula: see text], of a connected graph [Formula: see text], is the smallest positive integer such that from every placement of [Formula: see text] pebbles, [Formula: see text] pebbles can be moved to any specified target vertex by a sequence of pebbling moves, each move taking two pebbles off a vertex and placing one on an adjacent vertex. A graph [Formula: see text] satisfies the [Formula: see text]-pebbling property if [Formula: see text] pebbles can be moved to any specified vertex when the total starting number of pebbles is [Formula: see text], where [Formula: see text] is the number of vertices with at least one pebble. We show that the cycle [Formula: see text] satisfies the [Formula: see text]-pebbling property. Herscovici conjectured that for any connected graphs [Formula: see text] and [Formula: see text], [Formula: see text]. We prove Herscovici’s conjecture is true, when [Formula: see text] is an even cycle and for variety of graphs [Formula: see text] which satisfy the [Formula: see text]-pebbling property.

APA, Harvard, Vancouver, ISO, and other styles

Su, Zhenhua, and Zikai Tang. "Minimum distance–unbalancedness of the merged graph of $ C_3 $ and a tree." AIMS Mathematics 9, no. 7 (2024): 16863–75. http://dx.doi.org/10.3934/math.2024818.

Full text

Abstract:

<abstract>For a graph $ G $, let $ n_G(u, v) $ be the number of vertices of $ G $ that are strictly closer to $ u $ than to $ v $. The distance–unbalancedness index $ {\rm uB}(G) $ is defined as the sum of $ |n_G(u, v)-n_G(v, u)| $ over all unordered pairs of vertices $ u $ and $ v $ of $ G $. In this paper, we show that the minimum distance–unbalancedness of the merged graph $ C_3\cdot T $ is $ (n+2)(n-3) $, where $ C_3 \cdot T $ is obtained by attaching a tree $ T $ to the cycle $ C_3 $.</abstract>

APA, Harvard, Vancouver, ISO, and other styles

Bielak, Halina, and Kinga Dąbrowska. "The Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths." Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica 69, no. 2 (2015): 1. http://dx.doi.org/10.17951/a.2015.69.2.1-7.

Full text

Abstract:

The Ramsey number $R(G, H)$ for a pair of graphs $G$ and $H$ is defined as the smallest integer $n$ such that, for any graph $F$ on $n$ vertices, either $F$ contains $G$ or $\overline{F}$ contains $H$ as a subgraph, where $\overline{F}$ denotes the complement of $F$. We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers $R(K_1+L_n, P_m)$ and $R(K_1+L_n, C_m)$ for some integers $m$, $n$, where $L_n$ is a linear forest of order $n$ with at least one edge.

APA, Harvard, Vancouver, ISO, and other styles

Fachrunnisa, St Munieroh, Hasmawati Hasmawati, and Amir Kamal Amir. "Metric Dimension of Shackle Operation C_3 Cycle Graph." Jurnal Matematika, Statistika dan Komputasi 19, no. 2 (2023): 317–22. http://dx.doi.org/10.20956/j.v19i2.22957.

Full text

Abstract:

Let G be a connected graph and W be a ordered vertices subset on a connected graph . The set W is called resolving set for G if every vertex on graph G has distinct representation of W. A resolving set containing a minimum number of vertices is called resolving set minimum or basis for G and the cardinality of resolving set is the metric dimension on graph G, denoted by dim(G). In the thesis discusses about metric dimensions of shackle operation C3 cycle graph, dim(Shack(C31,C32,…,C3k:v31=v12,v32=v13,…,v3k-1=v1k ))=2 for k>=2 . To proof this results, we was used mathematical induction method.

APA, Harvard, Vancouver, ISO, and other styles

Kai-Siou, Wu, and Su-Tzu Juan Justie. "Mutually Independent Hamiltonian Cycles of Cn x Cn." May 27, 2012. https://doi.org/10.5281/zenodo.1082251.

Full text

Abstract:

In a graph G, a cycle is Hamiltonian cycle if it contain all vertices of G. Two Hamiltonian cycles C_1 = &lang;u_0, u_1, u_2, ..., u_{n−1}, u_0&rang; and C_2 = &lang;v_0, v_1, v_2, ..., v_{n−1}, v_0&rang; in G are independent if u_0 = v_0, u_i = ̸ v_i for all 1 ≤ i ≤ n−1. In G, a set of Hamiltonian cycles C = {C_1, C_2, ..., C_k} is mutually independent if any two Hamiltonian cycles of C are independent. The mutually independent Hamiltonicity IHC(G), = k means there exist a maximum integer k such that there exists k-mutually independent Hamiltonian cycles start from any vertex of G. In this paper, we prove that IHC(C_n × C_n) = 4, for n ≥ 3.

APA, Harvard, Vancouver, ISO, and other styles

"Cycle With Parallel Chords Are Odd Even Graceful." International Journal of Innovative Technology and Exploring Engineering 8, no. 11 (2019): 3103–7. http://dx.doi.org/10.35940/ijitee.k2494.0981119.

Full text

Abstract:

If C_n is a cycle of length n, then the graph cycle with parallel chords is obtained from C_n by adding an “edge “is the graph obtained by attaching a pendant edge at each vertex of the cycle” C_(n.) In this paper we prove that the graphs ncycle w for n≡0,3(mod 4). the graph P_(a,b) obtained by identifying the end points of a internally disjoint paths each of length b, are odd even graceful for odd values of a and b.

APA, Harvard, Vancouver, ISO, and other styles

Lin, Feng-Gen, and Lian-Zhu Zhang. "Pfaffian Orientation and Enumeration of Perfect Matchings for some Cartesian Products of Graphs." Electronic Journal of Combinatorics 16, no. 1 (2009). http://dx.doi.org/10.37236/141.

Full text

Abstract:

The importance of Pfaffian orientations stems from the fact that if a graph $G$ is Pfaffian, then the number of perfect matchings of $G$ (as well as other related problems) can be computed in polynomial time. Although there are many equivalent conditions for the existence of a Pfaffian orientation of a graph, this property is not well-characterized. The problem is that no polynomial algorithm is known for checking whether or not a given orientation of a graph is Pfaffian. Similarly, we do not know whether this property of an undirected graph that it has a Pfaffian orientation is in NP. It is well known that the enumeration problem of perfect matchings for general graphs is NP-hard. L. Lovász pointed out that it makes sense not only to seek good upper and lower bounds of the number of perfect matchings for general graphs, but also to seek special classes for which the problem can be solved exactly. For a simple graph $G$ and a cycle $C_n$ with $n$ vertices (or a path $P_n$ with $n$ vertices), we define $C_n$ (or $P_n)\times G$ as the Cartesian product of graphs $C_n$ (or $P_n$) and $G$. In the present paper, we construct Pfaffian orientations of graphs $C_4\times G$, $P_4\times G$ and $P_3\times G$, where $G$ is a non bipartite graph with a unique cycle, and obtain the explicit formulas in terms of eigenvalues of the skew adjacency matrix of $\overrightarrow{G}$ to enumerate their perfect matchings by Pfaffian approach, where $\overrightarrow{G}$ is an arbitrary orientation of $G$.

APA, Harvard, Vancouver, ISO, and other styles

LAN, KAIYANG, YIDONG ZHOU, and FENG LIU. "THE CHROMATIC NUMBER OF -FREE GRAPHS." Bulletin of the Australian Mathematical Society, October 3, 2022, 1–10. http://dx.doi.org/10.1017/s0004972722001034.

Full text

Abstract:

Abstract The diamond is the complete graph on four vertices minus one edge; $P_n$ and $C_n$ denote the path and cycle on n vertices, respectively. We prove that the chromatic number of a $(P_6,C_4,\mbox {diamond})$ -free graph G is no larger than the maximum of 3 and the clique number of G.

APA, Harvard, Vancouver, ISO, and other styles

Lidický, Bernard, Tomáš Masařík, Kyle Murphy, and Shira Zerbib. "On Weak Flexibility in Planar Graphs." Graphs and Combinatorics 38, no. 6 (2022). http://dx.doi.org/10.1007/s00373-022-02564-1.

Full text

Abstract:

AbstractRecently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447). In this new setting, each vertex v in some subset of V(G) has a request for a certain color r(v) in its list of colors L(v). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V, with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L-coloring of G satisfying at least $$\varepsilon |R|$$ ε | R | requests. If this is true, then $$\mathscr {C}$$ C is called $$\varepsilon$$ ε -flexible for lists of size k. Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021) introduced the notion of weak flexibility, where $$R = V$$ R = V . We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists $$\varepsilon (b)>0$$ ε ( b ) > 0 so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ K 4 , C 5 , C 6 , C 7 , B b is weakly $$\varepsilon (b)$$ ε ( b ) -flexible for lists of size 4 (here $$K_n$$ K n , $$C_n$$ C n and $$B_n$$ B n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ K 4 , C 5 , C 6 , C 7 , B 5 is $$\varepsilon$$ ε -flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable.

APA, Harvard, Vancouver, ISO, and other styles

Clemen, Felix Christian, Emily Heath, and Mikhail Lavrov. "Online Ramsey Numbers of Ordered Paths and Cycles." Electronic Journal of Combinatorics 31, no. 4 (2024). https://doi.org/10.37236/11610.

Full text

Abstract:

An ordered graph is a graph with a linear ordering on its vertices. The online Ramsey game for ordered graphs $G$ and $H$ is played on an infinite sequence of vertices; on each turn, Builder draws an edge between two vertices, and Painter colors it red or blue. Builder tries to create a red $G$ or a blue $H$ as quickly as possible, while Painter wants the opposite. The online ordered Ramsey number $r_o(G,H)$ is the number of turns the game lasts with optimal play. In this paper, we consider the behavior of $r_o(G,P_n)$ for fixed $G$, where $P_n$ is the monotone ordered path. We prove an $O(n \log n)$ bound on $r_o(G,P_n)$ for all $G$ and an $O(n)$ bound when $G$ is $3$-ichromatic; we partially classify graphs $G$ with $r_o(G,P_n) = n + O(1)$. Many of these results extend to $r_o(G,C_n)$, where $C_n$ is an ordered cycle obtained from $P_n$ by adding one edge.

APA, Harvard, Vancouver, ISO, and other styles

Kizhakkepallathu, Ashik Mathew, Patric RJ Östergård, and Alexandru Popa. "On the Shannon Capacity of Triangular Graphs." Electronic Journal of Combinatorics 20, no. 2 (2013). http://dx.doi.org/10.37236/3214.

Full text

Abstract:

The Shannon capacity of a graph $G$ is $c(G)=\sup_{d\geq 1}(\alpha(G^d))^{\frac{1}{d}},$ where $\alpha(G)$ is the independence number of $G$. The Shannon capacity of the Kneser graph $\mathrm{KG}_{n,r}$ was determined by Lovász in 1979, but little is known about the Shannon capacity of the complement of that graph when $r$ does not divide $n$. The complement of the Kneser graph, $\overline{\mathrm{KG}}_{n,2}$, is also called the triangular graph $T_n$. The graph $T_n$ has the $n$-cycle $C_n$ as an induced subgraph, whereby $c(T_n) \geq c(C_n)$, and these two families of graphs are closely related in the current context as both can be considered via geometric packings of the discrete $d$-dimensional torus of width $n$ using two types of $d$-dimensional cubes of width $2$. Bounds on $c(T_n)$ obtained in this work include $c(T_7) \geq \sqrt[3]{35} \approx 3.271$, $c(T_{13}) \geq \sqrt[3]{248} \approx 6.283$, $c(T_{15}) \geq \sqrt[4]{2802} \approx 7.276$, and $c(T_{21}) \geq \sqrt[4]{11441} \approx 10.342$.

APA, Harvard, Vancouver, ISO, and other styles

Atkins, Ross, Puck Rombach, and Fiona Skerman. "Guessing Numbers of Odd Cycles." Electronic Journal of Combinatorics 24, no. 1 (2017). http://dx.doi.org/10.37236/5964.

Full text

Abstract:

For a given number of colours, $s$, the guessing number of a graph is the base $s$ logarithm of the size of the largest family of colourings of the vertex set of the graph such that the colour of each vertex can be determined from the colours of the vertices in its neighbourhood. An upper bound for the guessing number of the $n$-vertex cycle graph $C_n$ is $n/2$. It is known that the guessing number equals $n/2$ whenever $n$ is even or $s$ is a perfect square. We show that, for any given integer $s \geq 2$, if $a$ is the largest factor of $s$ less than or equal to $\sqrt{s}$, for sufficiently large odd $n$, the guessing number of $C_n$ with $s$ colours is $(n-1)/2 + \log_s(a)$. This answers a question posed by Christofides and Markström in 2011.We also present an explicit protocol which achieves this bound for every $n$. Linking this to index coding with side information, we deduce that the information defect of $C_n$ with $s$ colours is $(n+1)/2 - \log_s(a)$ for sufficiently large odd $n$.

APA, Harvard, Vancouver, ISO, and other styles

Bradac, Domagoj, Nemanja Draganic, and Benny Sudakov. "Effective bounds for induced size-Ramsey numbers of cycles." European Conference on Combinatorics, Graph Theory and Applications, no. 12 (August 28, 2023). http://dx.doi.org/10.5817/cz.muni.eurocomb23-027.

Full text

Abstract:

The induced size-Ramsey number $\hat{r}_\text{ind}^k(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have such that for any $k$-coloring of its edges, there exists a monochromatic copy of $H$ which is an induced subgraph of $G$. In 1995, in their seminal paper, Haxell, Kohayakawa and {\L}uczak showed that for cycles, these numbers are linear for any constant number of colours, i.e., $\hat{r}_\text{ind}^k(C_n)\leq Cn$ for some $C=C(k)$. The constant $C$ comes from the use of the regularity lemma, and has a tower type dependence on $k$. In this paper we significantly improve these bounds, showing that $\hat{r}_\text{ind}^k(C_n)\leq O(k^{102})n$ when $n$ is even, thus obtaining only a polynomial dependence of $C$ on $k$. We also prove $\hat{r}_\text{ind}^k(C_n)\leq e^{O(k\log k)}n$ for odd $n$, which almost matches the lower bound of $e^{\Omega(k)}n$. Finally, we show that the ordinary (non-induced) size-Ramsey number satisfies $\hat{r}^k(C_n)=e^{O(k)}n$ for odd $n$. This substantially improves the best previous result of $e^{O(k^2)}n$, and is best possible, up to the implied constant in the exponent. To achieve our results, we present a new host graph construction which, roughly speaking, reduces our task to finding a cycle of approximate given length in a graph with local sparsity.

APA, Harvard, Vancouver, ISO, and other styles

Bradač, Domagoj, Nemanja Draganić, and Benny Sudakov. "Effective Bounds for Induced Size-Ramsey Numbers of Cycles." Combinatorica, May 14, 2024. http://dx.doi.org/10.1007/s00493-024-00103-5.

Full text

Abstract:

AbstractThe induced size-Ramsey number $$\hat{r}_\text {ind}^k(H)$$ r ^ ind k ( H ) of a graph H is the smallest number of edges a (host) graph G can have such that for any k-coloring of its edges, there exists a monochromatic copy of H which is an induced subgraph of G. In 1995, in their seminal paper, Haxell, Kohayakawa and Łuczak showed that for cycles, these numbers are linear for any constant number of colours, i.e., $$\hat{r}_\text {ind}^k(C_n)\le Cn$$ r ^ ind k ( C n ) ≤ C n for some $$C=C(k)$$ C = C ( k ) . The constant C comes from the use of the regularity lemma, and has a tower type dependence on k. In this paper we significantly improve these bounds, showing that $$\hat{r}_\text {ind}^k(C_n)\le O(k^{102})n$$ r ^ ind k ( C n ) ≤ O ( k 102 ) n when n is even, thus obtaining only a polynomial dependence of C on k. We also prove $$\hat{r}_\text {ind}^k(C_n)\le e^{O(k\log k)}n$$ r ^ ind k ( C n ) ≤ e O ( k log k ) n for odd n, which almost matches the lower bound of $$e^{\Omega (k)}n$$ e Ω ( k ) n . Finally, we show that the ordinary (non-induced) size-Ramsey number satisfies $$\hat{r}^k(C_n)=e^{O(k)}n$$ r ^ k ( C n ) = e O ( k ) n for odd n. This substantially improves the best previous result of $$e^{O(k^2)}n$$ e O ( k 2 ) n , and is best possible, up to the implied constant in the exponent. To achieve our results, we present a new host graph construction which, roughly speaking, reduces our task to finding a cycle of approximate given length in a graph with local sparsity.

APA, Harvard, Vancouver, ISO, and other styles

Alpert, Matthew, Elie Feder, and Heiko Harborth. "The Maximum of the Maximum Rectilinear Crossing Numbers of $d$-Regular Graphs of Order $n$." Electronic Journal of Combinatorics 16, no. 1 (2009). http://dx.doi.org/10.37236/143.

Full text

Abstract:

We extend known results regarding the maximum rectilinear crossing number of the cycle graph ($C_n$) and the complete graph ($K_n$) to the class of general $d$-regular graphs $R_{n,d}$. We present the generalized star drawings of the $d$-regular graphs $S_{n,d}$ of order $n$ where $n+d\equiv 1 \pmod 2 $ and prove that they maximize the maximum rectilinear crossing numbers. A star-like drawing of $S_{n,d}$ for $n \equiv d \equiv 0 \pmod 2$ is introduced and we conjecture that this drawing maximizes the maximum rectilinear crossing numbers, too. We offer a simpler proof of two results initially proved by Furry and Kleitman as partial results in the direction of this conjecture.

APA, Harvard, Vancouver, ISO, and other styles

He, Jinhua, Louis A. Valentin, Xiaoyan Yin, and Gexin Yu. "Extremal Permutations in Routing Cycles." Electronic Journal of Combinatorics 23, no. 3 (2016). http://dx.doi.org/10.37236/5422.

Full text

Abstract:

Let $G$ be a graph whose vertices are labeled $1,\ldots,n$, and $\pi$ be a permutation on $[n]:=\{1,2,\ldots, n\}$. A pebble $p_i$ that is initially placed at the vertex $i$ has destination $\pi(i)$ for each $i\in [n]$. At each step, we choose a matching and swap the two pebbles on each of the edges. Let $rt(G, \pi)$, the routing number for $\pi$, be the minimum number of steps necessary for the pebbles to reach their destinations.Li, Lu and Yang proved that $rt(C_n, \pi)\le n-1$ for every permutation $\pi$ on the $n$-cycle $C_n$ and conjectured that for $n\geq 5$, if $rt(C_n, \pi) = n-1$, then $\pi = 23\cdots n1$ or its inverse. By a computer search, they showed that the conjecture holds for $n<8$. We prove in this paper that the conjecture holds for all even $n\ge 6$.

APA, Harvard, Vancouver, ISO, and other styles

Pal, Hiranmoy, and Bikash Bhattacharjya. "Pretty Good State Transfer on Circulant Graphs." Electronic Journal of Combinatorics 24, no. 2 (2017). http://dx.doi.org/10.37236/6388.

Full text

Abstract:

Let $G$ be a graph with adjacency matrix $A$. The transition matrix of $G$ relative to $A$ is defined by $H(t):=\exp{\left(-itA\right)}$, where $t\in {\mathbb R}$. The graph $G$ is said to admit pretty good state transfer between a pair of vertices $u$ and $v$ if there exists a sequence of real numbers $\{t_k\}$ and a complex number $\gamma$ of unit modulus such that $\lim\limits_{k\rightarrow\infty} H(t_k) e_u=\gamma e_v.$ We find that the cycle $C_n$ as well as its complement $\overline{C}_n$ admit pretty good state transfer if and only if $n$ is a power of two, and it occurs between every pair of antipodal vertices. In addition, we look for pretty good state transfer in more general circulant graphs. We prove that union (edge disjoint) of an integral circulant graph with a cycle, each on $2^k$ $(k\geq 3)$ vertices, admits pretty good state transfer. The complement of such union also admits pretty good state transfer. Using Cartesian products, we find some non-circulant graphs admitting pretty good state transfer.

APA, Harvard, Vancouver, ISO, and other styles

Galvin, David, and Do Trong Thanh. "Stirling Numbers of Forests and Cycles." Electronic Journal of Combinatorics 20, no. 1 (2013). http://dx.doi.org/10.37236/3170.

Full text

Abstract:

For a graph $G$ and a positive integer $k$, the graphical Stirling number $S(G,k)$ is the number of partitions of the vertex set of $G$ into $k$ non-empty independent sets. Equivalently it is the number of proper colorings of $G$ that use exactly $k$ colors, with two colorings identified if they differ only on the names of the colors. If $G$ is the empty graph on $n$ vertices then $S(G,k)$ reduces to $S(n,k)$, the familiar Stirling number of the second kind.In this note we first consider Stirling numbers of forests. We show that if $(F^{c(n)}_n)_{n\geq 0}$ is any sequence of forests with $F^{c(n)}_n$ having $n$ vertices and $c(n)=o(\sqrt{n/\log n})$ components, and if $X^{c(n)}_n$ is a random variable that takes value $k$ with probability proportional to $S(F^{c(n)}_n,k)$ (that is, $X^{c(n)}_n$ is the number of classes in a uniformly chosen partition of $F^{c(n)}_n$ into non-empty independent sets), then $X^{c(n)}_n$ is asymptotically normal, meaning that suitably normalized it tends in distribution to the standard normal. This generalizes a seminal result of Harper on the ordinary Stirling numbers. Along the way we give recurrences for calculating the generating functions of the sequences $(S(F^c_n,k))_{k \geq 0}$, show that these functions have all real zeroes, and exhibit three different interlacing patterns between the zeroes of pairs of consecutive generating functions.We next consider Stirling numbers of cycles. We establish asymptotic normality for the number of classes in a uniformly chosen partition of $C_n$ (the cycle on $n$ vertices) into non-empty independent sets. We give a recurrence for calculating the generating function of the sequence $(S(C_n,k))_{k \geq 0}$, and use this to give a direct proof of a log-concavity result that had previously only been arrived at in a very indirect way.

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!