Log in

Relevant bibliographies by topics / K - connected graphs / Journal articles

To see the other types of publications on this topic, follow the link: K - connected graphs.

Journal articles on the topic 'K - connected graphs'

Author: Grafiati

Published: 4 June 2021

Last updated: 1 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 50 journal articles for your research on the topic 'K - connected graphs.'

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

CHENG, EDDIE, and MARC J. LIPMAN. "UNIDIRECTIONAL (n, k)-STAR GRAPHS." Journal of Interconnection Networks 03, no. 01n02 (March 2002): 19–34. http://dx.doi.org/10.1142/s0219265902000525.

Full text

Abstract:

Arrangement graphs14 and (n, k)-star graphs11 were introduced as generalizations of star graphs1. They were introduced to provide a wider set of choices for the order of topologically attractive interconnection networks. Unidirectional interconnection networks are more appropriate in many applications. Cheng and Lipman5, and Day and Tripathi17 studied the unidirectional star graphs, and Cheng and Lipman7 studied orientation of arrangement graphs. In this paper, we show that every (n, k)-star graph can be oriented to a maximally arc-connected graph when the regularity of the graph is even. If the regularity is odd, then the resulting directed graph can be augmented to a maximally arc-connected directed graph by adding a directed matching. In either case, the diameter of the resulting directed graph is small. Moreover, there exists a simple and near-optimal routing algorithm.

APA, Harvard, Vancouver, ISO, and other styles

2

Ando, Kiyoshi, and Yoko Usami. "Critically (k, k)-connected graphs." Discrete Mathematics 66, no. 1-2 (August 1987): 15–20. http://dx.doi.org/10.1016/0012-365x(87)90114-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Marhelina, Sally. "RAINBOW CONNECTION PADA GRAF k -CONNECTED UNTUK k = 1 ATAU 2." Jurnal Matematika UNAND 2, no. 1 (March 10, 2013): 78. http://dx.doi.org/10.25077/jmu.2.1.78-84.2013.

Full text

Abstract:

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of aconnected graph G, denoted by rc(G) is the smallest number of colors needed such thatG is rainbow connected. In this paper, we will proved again that rc(G) ≤ 3(n + 1)/5 forall 3-connected graphs, and rc(G) ≤ 2n/3 for all 2-connected graphs.

APA, Harvard, Vancouver, ISO, and other styles

4

Mynhardt, C. M., L. E. Teshima, and A. Roux. "Connected k-dominating graphs." Discrete Mathematics 342, no. 1 (January 2019): 145–51. http://dx.doi.org/10.1016/j.disc.2018.09.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Hong, Zhen-Mu, Zheng-Jiang Xia, Fuyuan Chen, and Lutz Volkmann. "Sufficient Conditions for Graphs to Be k -Connected, Maximally Connected, and Super-Connected." Complexity 2021 (February 22, 2021): 1–11. http://dx.doi.org/10.1155/2021/5588146.

Full text

Abstract:

Let G be a connected graph with minimum degree δ G and vertex-connectivity κ G . The graph G is k -connected if κ G ≥ k , maximally connected if κ G = δ G , and super-connected if every minimum vertex-cut isolates a vertex of minimum degree. In this paper, we present sufficient conditions for a graph with given minimum degree to be k -connected, maximally connected, or super-connected in terms of the number of edges, the spectral radius of the graph, and its complement, respectively. Analogous results for triangle-free graphs with given minimum degree to be k -connected, maximally connected, or super-connected are also presented.

APA, Harvard, Vancouver, ISO, and other styles

6

Hennayake, Kamal, Hong-Jian Lai, Deying Li, and Jingzhong Mao. "Minimally (k, k)-edge-connected graphs." Journal of Graph Theory 44, no. 2 (September 9, 2003): 116–31. http://dx.doi.org/10.1002/jgt.10132.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Shen, Yuanyuan, Xinhui An, and Baonyindureng Wu. "Hamilton-Connected Mycielski Graphs∗." Discrete Dynamics in Nature and Society 2021 (September 15, 2021): 1–7. http://dx.doi.org/10.1155/2021/3376981.

Full text

Abstract:

Jarnicki, Myrvold, Saltzman, and Wagon conjectured that if G is Hamilton-connected and not K 2 , then its Mycielski graph μ G is Hamilton-connected. In this paper, we confirm that the conjecture is true for three families of graphs: the graphs G with δ G > V G / 2 , generalized Petersen graphs G P n , 2 and G P n , 3 , and the cubes G 3 . In addition, if G is pancyclic, then μ G is pancyclic.

APA, Harvard, Vancouver, ISO, and other styles

8

Karpov, D. V. "Blocks in k-connected graphs." Journal of Mathematical Sciences 126, no. 3 (March 2005): 1167–81. http://dx.doi.org/10.1007/s10958-005-0084-4.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Egawa, Yoshimi. "k-shredders ink-connected graphs." Journal of Graph Theory 59, no. 3 (November 2008): 239–59. http://dx.doi.org/10.1002/jgt.20336.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

Devillers, Alice, Joanna B. Fawcett, Cheryl E. Praeger, and Jin-Xin Zhou. "On k-connected-homogeneous graphs." Journal of Combinatorial Theory, Series A 173 (July 2020): 105234. http://dx.doi.org/10.1016/j.jcta.2020.105234.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Dudek, Andrzej, Esmeralda Năstase, and Vojtěch Rödl. "On k-chromatically connected graphs." Discrete Mathematics 309, no. 18 (September 2009): 5547–50. http://dx.doi.org/10.1016/j.disc.2008.03.023.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

Obraztsova, S. A. "Cliques in k-connected graphs." Journal of Mathematical Sciences 145, no. 3 (September 2007): 4975–80. http://dx.doi.org/10.1007/s10958-007-0332-x.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Gurgel, M. A., and Y. Wakabayashi. "On k-leaf-connected graphs." Journal of Combinatorial Theory, Series B 41, no. 1 (August 1986): 1–16. http://dx.doi.org/10.1016/0095-8956(86)90023-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Oellermann, Ortrud R. "Major n-connected graphs." Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics 47, no. 1 (August 1989): 43–52. http://dx.doi.org/10.1017/s1446788700031189.

Full text

Abstract:

AbstractAn induced subgraph H of connectivity (edge-connectivity) n in a graph G is a major n-connected (major n-edge-connected) subgraph of G if H contains no subgraph with connectivity (edge- connectivity) exceeding n and H has maximum order with respect to this property. An induced subgraph is a major (major edge-) subgraph if it is a major n-connected (major n-edge-connected) subgraph for some n. Let m be the maximum order among all major subgraphs of C. Then the major connectivity set K(G) of G is defined as the set of all n for which there exists a major n-connected subgraph of G having order m. The major edge-connectivity set is defined analogously. The connectivity and the elements of the major connectivity set of a graph are compared, as are the elements of the major connectivity set and the major edge-connectivity set of a graph. It is shown that every set S of nonnegative integers is the major connectivity set of some graph G. Further, it is shown that for each positive integer m exceeding every element of S, there exists a graph G such that every major k-connected subgraph of G, where k ∈ K(G), has order m. Moreover, upper and lower bounds on the order of such graphs G are established.

APA, Harvard, Vancouver, ISO, and other styles

15

Egawa, Yoshimi. "Cycles in k-connected graphs whose deletion results in a (k-2)-connected graph." Journal of Combinatorial Theory, Series B 42, no. 3 (June 1987): 371–77. http://dx.doi.org/10.1016/0095-8956(87)90053-0.

Full text

APA, Harvard, Vancouver, ISO, and other styles

16

Engel, Konrad, and Sven Guttmann. "Testing Bandwidth k for k-Connected Graphs." SIAM Journal on Discrete Mathematics 16, no. 2 (January 2003): 301–12. http://dx.doi.org/10.1137/s0895480199351148.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Junming, Xu, and Xu Keli. "On k-diameter of k-connected graphs." Applied Mathematics-A Journal of Chinese Universities 16, no. 3 (September 2001): 231–36. http://dx.doi.org/10.1007/s11766-001-0059-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Cai, Mao-cheng. "Connected [k, k + 1]-factors of graphs." Discrete Mathematics 169, no. 1-3 (May 1997): 1–16. http://dx.doi.org/10.1016/0012-365x(95)00328-t.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

FUJISAWA, JUN, and AKIRA SAITO. "A Pair of Forbidden Subgraphs and 2-Factors." Combinatorics, Probability and Computing 21, no. 1-2 (February 2, 2012): 149–58. http://dx.doi.org/10.1017/s0963548311000514.

Full text

Abstract:

In this paper, we consider pairs of forbidden subgraphs that imply the existence of a 2-factor in a graph. For d ≥ 2, let d be the set of connected graphs of minimum degree at least d. Let F1 and F2 be connected graphs and let be a set of connected graphs. Then {F1, F2} is said to be a forbidden pair for if every {F1, F2}-free graph in of sufficiently large order has a 2-factor. Faudree, Faudree and Ryjáček have characterized all the forbidden pairs for the set of 2-connected graphs. We first characterize the forbidden pairs for 2, which is a larger set than the set of 2-connected graphs, and observe a sharp difference between the characterized pairs and those obtained by Faudree, Faudree and Ryjáček. We then consider the forbidden pairs for connected graphs of large minimum degree. We prove that if {F1, F2} is a forbidden pair for d, then either F1 or F2 is a star of order at most d + 2. Ota and Tokuda have proved that every $K_{1, \lfloor\frac{d+2}{2}\rfloor}$-free graph of minimum degree at least d has a 2-factor. These results imply that for k ≥ d + 2, no connected graphs F except for stars of order at most d + 2 make {K1,k, F} a forbidden pair for d, while for $k\le \bigl\lfloor\frac{d+2}{2} \bigr\rfloor$ every connected graph F makes {K1,k, F} a forbidden pair for d. We consider the remaining range of $\bigl\lfloor\frac{d+2}{2} \bigr\rfloor < k < d+2$, and prove that only a finite number of connected graphs F make {K1,k, F} a forbidden pair for d.

APA, Harvard, Vancouver, ISO, and other styles

20

Su, Jianji, Xiaofeng Guo, and Liqiong Xu. "Removable edges in a k-connected graph and a construction method for k-connected graphs." Discrete Mathematics 309, no. 10 (May 2009): 3161–65. http://dx.doi.org/10.1016/j.disc.2008.09.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Kok, Johan. "Heuristic method to determine lucky k-polynomials for k-colorable graphs." Acta Universitatis Sapientiae, Informatica 11, no. 2 (December 1, 2019): 206–14. http://dx.doi.org/10.2478/ausi-2019-0014.

Full text

Abstract:

Abstract The existence of edges is a huge challenge with regards to determining lucky k-polynomials of simple connected graphs in general. In this paper the lucky 3-polynomials of path and cycle graphs of order, 3 ≤ n ≤ 8 are presented as the basis for the heuristic method to determine the lucky k-polynomials for k-colorable graphs. The difficulty of adjacency with graphs is illustrated through these elementary graph structures. The results are also illustratively compared with the results for null graphs (edgeless graphs). The paper could serve as a basis for finding recurrence results through innovative methodology.

APA, Harvard, Vancouver, ISO, and other styles

22

Larose, Benoit. "Strongly Projective Graphs." Canadian Journal of Mathematics 54, no. 4 (August 1, 2002): 757–68. http://dx.doi.org/10.4153/cjm-2002-029-7.

Full text

Abstract:

AbstractWe introduce the notion of strongly projective graph, and characterise these graphs in terms of their neighbourhood poset. We describe certain exponential graphs associated to complete graphs and odd cycles. We extend and generalise a result of Greenwell and Lovász [6]: if a connected graph G does not admit a homomorphism to K, where K is an odd cycle or a complete graph on at least 3 vertices, then the graph G × Ks admits, up to automorphisms of K, exactly s homomorphisms to K.

APA, Harvard, Vancouver, ISO, and other styles

23

Chen, Jessica, Le Chen, and Derrick Liu. "Intersections of Cycles in $$k$$ k -Connected Graphs." Graphs and Combinatorics 31, no. 4 (April 26, 2014): 897–914. http://dx.doi.org/10.1007/s00373-014-1427-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Gupta, Arvind, Naomi Nishimura, Andrzej Proskurowski, and Prabhakar Ragde. "Embeddings of k-connected graphs of pathwidth k." Discrete Applied Mathematics 145, no. 2 (January 2005): 242–65. http://dx.doi.org/10.1016/j.dam.2002.12.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Kirkland, Steve, Israel Rocha, and Vilmar Trevisan. "Algebraic connectivity of k-connected graphs." Czechoslovak Mathematical Journal 65, no. 1 (March 2015): 219–36. http://dx.doi.org/10.1007/s10587-015-0170-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Schiermeyer, Ingo. "On minimally rainbow k-connected graphs." Discrete Applied Mathematics 161, no. 4-5 (March 2013): 702–5. http://dx.doi.org/10.1016/j.dam.2011.05.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Huang, Xiaolong, Zemin Jin, Xingxing Yu, and Xiaoyan Zhang. "Contractible Cliques in k-Connected Graphs." Graphs and Combinatorics 22, no. 3 (November 2006): 361–70. http://dx.doi.org/10.1007/s00373-006-0670-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Ding, Guoli, and Emily Marshall. "Minimal k-Connected Non-Hamiltonian Graphs." Graphs and Combinatorics 34, no. 2 (February 14, 2018): 289–312. http://dx.doi.org/10.1007/s00373-018-1874-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Glazman, A. "Generalized flowers in k-connected graphs." Journal of Mathematical Sciences 184, no. 5 (June 30, 2012): 579–94. http://dx.doi.org/10.1007/s10958-012-0883-3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Sun, Yuefang, Zemin Jin, and Fengwei Li. "On total rainbow k -connected graphs." Applied Mathematics and Computation 311 (October 2017): 223–27. http://dx.doi.org/10.1016/j.amc.2017.05.020.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Okamura, Haruko. "Paths in k-edge-connected graphs." Journal of Combinatorial Theory, Series B 45, no. 3 (December 1988): 345–55. http://dx.doi.org/10.1016/0095-8956(88)90077-9.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Heydemann, M. C., J. C. Meyer, J. Opatrny, and D. Sotteau. "Forwarding indices of k-connected graphs." Discrete Applied Mathematics 37-38 (July 1992): 287–96. http://dx.doi.org/10.1016/0166-218x(92)90140-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Asif, Muhammad, Hamad Almohamedh, Muhammad Hussain, Khalid M. Alhamed, Abdulrazaq A. Almutairi, and Sultan Almotairi. "An Approach to the Geometric-Arithmetic Index for Graphs under Transformations’ Fact over Pendent Paths." Complexity 2021 (June 24, 2021): 1–13. http://dx.doi.org/10.1155/2021/3745862.

Full text

Abstract:

Graph theory is a dynamic tool for designing and modeling of an interconnection system by a graph. The vertices of such graph are processor nodes and edges are the connections between these processors nodes. The topology of a system decides its best use. Geometric-arithmetic index is one of the most studied graph invariant to characterize the topological aspects of underlying interconnection networks or graphs. Transformation over graph is also an important tool to define new network of their own choice in computer science. In this work, we discuss transformed family of graphs. Let Γ n k , l be the connected graph comprises by k number of pendent path attached with fully connected vertices of the n-vertex connected graph Γ . Let A α Γ n k , l and A α β Γ n k , l be the transformed graphs under the fact of transformations A α and A α β , 0 ≤ α ≤ l , 0 ≤ β ≤ k − 1 , respectively. In this work, we obtained new inequalities for the graph family Γ n k , l and transformed graphs A α Γ n k , l and A α β Γ n k , l which involve GA Γ . The presence of GA Γ makes the inequalities more general than all those which were previously defined for the GA index. Furthermore, we characterize extremal graphs which make the inequalities tight.

APA, Harvard, Vancouver, ISO, and other styles

34

Wenni, Mariza. "BILANGAN KROMATIK LOKASI DARI GRAF P m P n ; K m P n ; DAN K , m K n." Jurnal Matematika UNAND 2, no. 1 (March 10, 2013): 14. http://dx.doi.org/10.25077/jmu.2.1.14-22.2013.

Full text

Abstract:

Let G and H be two connected graphs. Let c be a vertex k-coloring of aconnected graph G and let = fCg be a partition of V (G) into the resultingcolor classes. For each v 2 V (G), the color code of v is dened to be k-vector: c1; C2; :::; Ck(v) =(d(v; C1); d(v; C2); :::; d(v; Ck)), where d(v; Ci) = minfd(v; x) j x 2 Cg, 1 i k. Ifdistinct vertices have distinct color codes with respect to , then c is called a locatingcoloring of G. The locating chromatic number of G is the smallest natural number ksuch that there are locating coloring with k colors in G. The Cartesian product of graphG and H is a graph with vertex set V (G) V (H), where two vertices (a; b) and (a)are adjacent whenever a = a0and bb02 E(H), or aa0i2 E(G) and b = b, denotedby GH. In this paper, we will study about the locating chromatic numbers of thecartesian product of two paths, the cartesian product of paths and complete graphs, andthe cartesian product of two complete graphs.

APA, Harvard, Vancouver, ISO, and other styles

35

Cicerone, Serafino. "A Quasi-Hole Detection Algorithm for Recognizing k-Distance-Hereditary Graphs, with k < 2." Algorithms 14, no. 4 (March 25, 2021): 105. http://dx.doi.org/10.3390/a14040105.

Full text

Abstract:

Cicerone and Di Stefano defined and studied the class of k-distance-hereditary graphs, i.e., graphs where the distance in each connected induced subgraph is at most k times the distance in the whole graph. The defined graphs represent a generalization of the well known distance-hereditary graphs, which actually correspond to 1-distance-hereditary graphs. In this paper we make a step forward in the study of these new graphs by providing characterizations for the class of all the k-distance-hereditary graphs such that k<2. The new characterizations are given in terms of both forbidden subgraphs and cycle-chord properties. Such results also lead to devise a polynomial-time recognition algorithm for this kind of graph that, according to the provided characterizations, simply detects the presence of quasi-holes in any given graph.

APA, Harvard, Vancouver, ISO, and other styles

36

Tomescu, Ioan, Misbah Arshad, and Muhammad Jamil. "Extremal topological indices for graphs of given connectivity." Filomat 29, no. 7 (2015): 1639–43. http://dx.doi.org/10.2298/fil1507639t.

Full text

Abstract:

In this paper, we show that in the class of graphs of order n and given (vertex or edge) connectivity equal to k (or at most equal to k), 1 ? k ? n - 1, the graph Kk + (K1? Kn-k-1) is the unique graph such that zeroth-order general Randic index, general sum-connectivity index and general Randic connectivity index are maximum and general hyper-Wiener index is minimum provided ? > 1. Also, for 2-connected (or 2-edge connected) graphs and ? > 0 the unique graph minimizing these indices is the n-vertex cycle Cn.

APA, Harvard, Vancouver, ISO, and other styles

37

ZHANG, YINGYING, and XIAOYU ZHU. "Proper Vertex Connection and Graph Operations." Journal of Interconnection Networks 19, no. 02 (June 2019): 1950001. http://dx.doi.org/10.1142/s0219265919500014.

Full text

Abstract:

A path in a vertex-colored graph is a vertex-proper path if any two internal adjacent vertices differ in color. A vertex-colored graph is proper vertex k-connected if any two vertices of the graph are connected by k disjoint vertex-proper paths of the graph. For a k-connected graph G, the proper vertex k-connection number of G, denoted by pvck(G), is defined as the smallest number of colors required to make G proper vertex k-connected. A vertex-colored graph is strong proper vertex-connected, if for any two vertices u, v of the graph, there exists a vertex-proper u-v geodesic. For a connected graph G, the strong proper vertex-connection number of G, denoted by spvc(G), is the smallest number of colors required to make G strong proper vertex-connected. In this paper, we study the proper vertex k-connection number and the strong proper vertex-connection number on the join of two graphs, the Cartesian, lexicographic, strong and direct product, and present exact values or upper bounds for these operations of graphs. Then we apply these results to some instances of Cartesian and lexicographic product networks.

APA, Harvard, Vancouver, ISO, and other styles

38

NARAYANASWAMY, N. S., and N. SADAGOPAN. "A UNIFIED FRAMEWORK FOR BI(TRI)CONNECTIVITY AND CHORDAL AUGMENTATION." International Journal of Foundations of Computer Science 24, no. 01 (January 2013): 67–93. http://dx.doi.org/10.1142/s0129054113400054.

Full text

Abstract:

For a connected non-complete graph, a vertex separator is a subset of vertices whose deletion increases the number of connected components and the vertex connectivity of the graph refers to the size of a minimum vertex separator. A graph with the vertex connectivity k is said to be k-vertex connected. Given a k-vertex connected graph G, vertex connectivity augmentation determines a smallest set of edges whose augmentation to G makes it (k + 1)-vertex connected. In this paper, we report our study on connectivity augmentation in 1-connected graphs, 2-connected graphs, and k-connected chordal graphs. We first represent the graph under consideration using a "tree-like" graph. This tree is unique and explicitly captures the connectivity information of the graph. Using this tree, our proposed data structure maintains the set of equivalence classes based on an equivalence relation on the set of leaves of the tree. This partition determines a set of edges to be augmented to increase the connectivity of the graph by one. Based on our data structure, we present a new combinatorial analysis and an elegant proof of correctness of our linear-time algorithm for an optimum connectivity augmentation. The novelty is in the data structure which is a unified framework for all three augmentations. As far as the run-time analysis is concerned, given the associated tree, our approach yields an augmentation set in linear time.

APA, Harvard, Vancouver, ISO, and other styles

39

Bent-Usman, Wardah Masanggila, Rowena Isla, and Sergio Canoy. "Neighborhood Connected k-Fair Domination Under Some Binary Operations." European Journal of Pure and Applied Mathematics 12, no. 3 (August 2, 2019): 1337–49. http://dx.doi.org/10.29020/nybg.ejpam.v12i3.3506.

Full text

Abstract:

Let G=(V(G),E(G)) be a simple graph. A neighborhood connected k-fair dominating set (nckfd-set) is a dominating set S subset V(G) such that |N(u) intersection S|=k for every u is an element of V(G)\S and the induced subgraph of S is connected. In this paper, we introduce and invistigate the notion of neighborhood connected k-fair domination in graphs. We also characterize such dominating sets in the join, corona, lexicographic and cartesians products of graphs and determine the exact value or sharp bounds of their corresponding neighborhood connected k-fair domination number.

APA, Harvard, Vancouver, ISO, and other styles

40

Bueno, Letícia, Luerbio Faria, Figueiredo De, and Fonseca Da. "Hamiltonian paths in odd graphs." Applicable Analysis and Discrete Mathematics 3, no. 2 (2009): 386–94. http://dx.doi.org/10.2298/aadm0902386b.

Full text

Abstract:

Lov?sz conjectured that every connected vertex-transitive graph has a Hamiltonian path. The odd graphs Ok form a well-studied family of connected, k-regular, vertex-transitive graphs. It was previously known that Ok has Hamiltonian paths for k ? 14. A direct computation of Hamiltonian paths in Ok is not feasible for large values of k, because Ok has (2k - 1, k - 1) vertices and k/2 (2k - 1, k - 1) edges. We show that Ok has Hamiltonian paths for 15 ? k ? 18. Instead of directly running any heuristics, we use existing results on the middle levels problem, therefore further relating these two fundamental problems, namely finding a Hamiltonian path in the odd graph and finding a Hamiltonian cycle in the corresponding middle levels graph. We show that further improved results for the middle levels problem can be used to find Hamiltonian paths in Ok for larger values of k.

APA, Harvard, Vancouver, ISO, and other styles

41

Hou, Xinmin, and Tianming Wang. "ON GENERALIZED k-DIAMETER OF k-REGULAR k-CONNECTED GRAPHS." Taiwanese Journal of Mathematics 8, no. 4 (December 2004): 739–45. http://dx.doi.org/10.11650/twjm/1500407715.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Frank Hsu, D., and Tomasz Łuczak. "On the k-diameter of k-regular k-connected graphs." Discrete Mathematics 133, no. 1-3 (October 1994): 291–96. http://dx.doi.org/10.1016/0012-365x(94)90036-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

43

Iqbal, Tanveer, Muhammad Naeem Azhar, and Syed Ahtsham Ul Haq Bokhary. "The K -Size Edge Metric Dimension of Graphs." Journal of Mathematics 2020 (December 31, 2020): 1–7. http://dx.doi.org/10.1155/2020/1023175.

Full text

Abstract:

In this paper, a new concept k -size edge resolving set for a connected graph G in the context of resolvability of graphs is defined. Some properties and realizable results on k -size edge resolvability of graphs are studied. The existence of this new parameter in different graphs is investigated, and the k -size edge metric dimension of path, cycle, and complete bipartite graph is computed. It is shown that these families have unbounded k -size edge metric dimension. Furthermore, the k-size edge metric dimension of the graphs Pm □ Pn, Pm □ Cn for m, n ≥ 3 and the generalized Petersen graph is determined. It is shown that these families of graphs have constant k -size edge metric dimension.

APA, Harvard, Vancouver, ISO, and other styles

44

BHABAK, PUSPAL, and HOVHANNES A. HARUTYUNYAN. "Approximation Algorithm for the Broadcast Time in k-Path Graph." Journal of Interconnection Networks 19, no. 04 (December 2019): 1950006. http://dx.doi.org/10.1142/s0219265919500063.

Full text

Abstract:

Broadcasting is an information dissemination problem in a connected network in which one node, called the originator, must distribute a message to all other nodes by placing a series of calls along the communication lines of the network. In every unit of time, the informed nodes aid the originator in distributing the message. Finding the broadcast time of any vertex in an arbitrary graph is NP-complete. The polynomial time solvability is shown only for certain graphs like trees, unicyclic graphs, tree of cycles, necklace graphs, fully connected trees and tree of cliques. In this paper we study the broadcast problem in k-path graphs. For any originator of the k-path graph we present a (4 – ϵ)-approximation algorithm in the worst case. The algorithm gives a better approximation ratio for some large classes of k-path graphs. Moreover, our algorithm generates the optimal broadcast time for some cases.

APA, Harvard, Vancouver, ISO, and other styles

45

LI, XIAOJUAN, BING WEI, and YONGJIN ZHU. "CYCLES IN TRIANGLE-FREE GRAPHS." Discrete Mathematics, Algorithms and Applications 03, no. 03 (September 2011): 343–56. http://dx.doi.org/10.1142/s1793830911001267.

Full text

Abstract:

Let G be a k-connected (k ≥ 3), triangle-free graph with α(G) ≤ k + 1. If G is not Petersen graph and G ∉ {Kk, k, Kk, k + 1, Kk + 1, k+1}, then G contains cycles of lengths from 4 to |V(G)|. This generalizes a result conjectured by Amar et al. (Graphs Combin.7 (1991)) and proved by Lou (Discrete Math.152 (1996)).

APA, Harvard, Vancouver, ISO, and other styles

46

Jordán, Tibor. "On minimally k-edge-connected graphs and shortest k-edge-connected Steiner networks." Discrete Applied Mathematics 131, no. 2 (September 2003): 421–32. http://dx.doi.org/10.1016/s0166-218x(02)00465-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Volkmann, Lutz. "Connected global offensive k-alliances in graphs." Discussiones Mathematicae Graph Theory 31, no. 4 (2011): 699. http://dx.doi.org/10.7151/dmgt.1574.

Full text

APA, Harvard, Vancouver, ISO, and other styles

48

Ando, Kiyoshi, Atsushi Kaneko, and Ken-ichi Kawarabayashi. "Contractible edges in minimally k-connected graphs." Electronic Notes in Discrete Mathematics 11 (July 2002): 20–29. http://dx.doi.org/10.1016/s1571-0653(04)00052-6.

Full text

APA, Harvard, Vancouver, ISO, and other styles

49

Zhang, Shenggui, Bing Chen, and Rongzu Yu. "Heavy cycles in k-connected weighted graphs." Electronic Notes in Discrete Mathematics 17 (October 2004): 293–96. http://dx.doi.org/10.1016/j.endm.2004.03.053.

Full text

APA, Harvard, Vancouver, ISO, and other styles

50

Li, Shougui. "On connected k-domination numbers of graphs." Discrete Mathematics 274, no. 1-3 (January 2004): 303–10. http://dx.doi.org/10.1016/s0012-365x(03)00203-6.

Full text

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!