Search

Let G be either a complete graph of odd order or a complete bipartite graph in which each vertex partition has an even number of vertices. In this paper, we determine the set of triples (p, q, r), with p, q, r > 0, for which there exists a decomposition of G into p paths, q stars, and r cycles, each of which has 4 edges.

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\).

We define a total k-labeling of a graph G as a combination of an edge labeling and a vertex labeling such that if and if where The total k-labeling is called an edge irregular reflexive k-labeling of G if every two different edges has distinct edge weights, where the edge weight is defined as the summation of the edge label itself and its two vertex labels. Thus, the smallest value of k for which the graph G has the edge irregular reflexive k-labeling is called the reflexive edge strength of G. In this paper, we study the edge irregular reflexive labeling of corona product of two paths and corona product of a path with isolated vertices. We determine the reflexive edge strength for these graphs.

The length of a shortest path between two vertices u and v in a simple and connected graph G, denoted by d(u, v), is called the distance of u and v. An inclusive vertex irregular d-distance labeling is a labeling defined as such that the vertex weight, that is are all distinct. The minimal value of the largest label used over all such labeling of graph G, denoted by is defined as inclusive d-distance irregularity strength of G. Others studies have concluded the lower bound value of and the value of In this paper, we generalize the lower bound value of for We used the lower bound value of and the previous result of to investigate the value of As a result, we found the exact values of for the cases n = 7, and the value of the upper bound of for other n. We also found the relation of the value of and the value of Further investigation on path brought us to conclude the exact value of and for some n.

Let Sk and Kk respectively denote a path, a star and a complete graph on k vertices. By a -decomposition of a graph G, we mean a decomposition of G into r copies of and s copies of In this paper, it shown that the graph admits a -decomposition if and only if where denotes a tensor product of complete graphs. Also we extend the existence of such a decomposition in complete m-partite graphs.

The crossing number of a graph G, Cr(G) is the minimum number of edge crossings overall good drawings of G. Among the well-known four standard graph products namely Cartesian product, Kronecker product, strong product and lexicographic product, the one that is most difficult to deal with is the Kronecker product. P.K. Jha and S. Devishetty have analyzed the upper bounds for crossing number of Kronecker product of two cycles in, “Orthogonal Drawings and the Crossing Numbers of the Kronecker product of two cycles”, J. Parallel Distrib. Comput. 72 (2012), 195–204. For any graph G except and K4 of order at most four, the graph is planar. In this paper, we establish the crossing number of Kronecker product of a complete tripartite graph with path and as a corollary, we show that its rectilinear crossing number is same as its crossing number. Also, we give the open problems on the crossing number of above mentioned graphs.

For simple graphs G and H the size multipartite Ramsey number mj ( G , H ) is the smallest natural number t such that any arbitrary red-blue coloring on the edges of Kjxt contains a red G or a blue H as a subgraph. We studied the size tripartite Ramsey numbers m 3( G , H ) where G=mK1,n and H=P3 . In this paper, we generalize this result. We determine m3(G,H) where G is a star forest, namely a disjoint union of heterogeneous stars, and H=P3 . Moreover, we also determine m2(G,H) for this pair of graphs G and H .

For any pair of graphs G and H, both the size Ramsey number ̂r(G,H) and the restricted size Ramsey number r*(G,H) are bounded above by the size of the complete graph with order equals to the Ramsey number r(G,H), and bounded below by e(G) + e(H) − 1. Moreover, trivially, ̂r(G,H) ≤ r*(G,H). When introducing the size Ramsey number for graph, Erdős et al. (1978) asked two questions; (1) Do there exist graphs G and H such that ˆr(G,H) attains the upper bound? and (2) Do there exist graphs G and H such that ̂r(G,H) is significantly less than the upper bound?

The main aim of the paper is to establish the crossing numbers of the join products of the paths and the cycles on n vertices with a connected graph on five vertices isomorphic to the graph K1,1,3\e obtained by removing one edge e incident with some vertex of order two from the complete tripartite graph K1,1,3. The proofs are done with the help of well-known exact values for the crossing numbers of the join products of subgraphs of the considered graph with paths and cycles. Finally, by adding some edges to the graph under consideration, we obtain the crossing numbers of the join products of other graphs with the paths and the cycles on n vertices.

In this paper we consider the complex uniformly resolvable decompositions of the complete graph $K_v$ into subgraphs such that each resolution class contains only blocks isomorphic to the same graph from a given set $\mathcal H$. We completely determine the spectrum for the cases $\mathcal{H} = \{K_2, P_3, K_3\}$, $\mathcal{H} = \{P_4, C_4\}$, and $\mathcal{H} = \{K_2, P_4, C_4\}$., Comment: 11 pages

Algorithmic decidability is established for two order-theoretic properties of downward closed subsets defined by finitely many obstructions in two infinite posets. The properties under consideration are: (a) being atomic, i.e. not being decomposable as a union of two downward closed proper subsets, or, equivalently, satisfying the joint embedding property; and (b) being well quasi-ordered. The two posets are: (1) words over a finite alphabet under the consecutive subword ordering; and (2) finite permutations under the consecutive subpermutation ordering. Underpinning the four results are characterisations of atomicity and well quasi-order for the subpath ordering on paths of a finite directed graph. Postprint

A signed graph Γ is said to be determined by its spectrum if every signed graph with the same spectrum as Γ is switching isomorphic with Γ. Here it is proved that the path P n , interpreted as a signed graph, is determined by its spectrum if and only if n ≡ 0 , 1 , or 2 (mod 4), unless n ∈ { 8 , 13 , 14 , 17 , 29 } , or n = 3 .

Let G be a ( p , q ) -graph. Let f : V ( G ) → {1, 2, …, k } be a map where k is an integer, 2 ≤ k ≤ p . For each edge u v , assign the label ∣ f ( u ) − f ( v )∣ . f is called k -difference cordial labeling of G if ∣ v f ( i ) − v f ( j )∣ ≤ 1 and ∣ e f (0) − e f (1)∣ ≤ 1 where v f ( x ) denotes the number of vertices labelled with x , e f (1) and e f (0) respectively denote the number of edges labelled with 1 and not labelled with 1 . A graph with a k -difference cordial labeling is called a k -difference cordial graph. In this paper we investigate 3 -difference cordial labeling behavior of triangular snake, alternate triangular snake, alternate quadrilateral snake, irregular triangular snake, irregular quadrilateral snake, double triangular snake, double quadrilateral snake, double alternate triangular snake, and double alternate quadrilateral snake.

For a fixed graph [math] , a graph [math] is [math] -linked if any injection [math] can be extended to an [math] -subdivision in [math] . The concept of [math] -linked generalizes several well-known graph theory concepts such as [math] -connected, [math] -linked, and [math] -ordered. In 2012, Ferrara et al. proved a sharp [math] (or degree-sum) bound for a graph to be [math] -linked. In particular, they proved that any graph [math] with [math] vertices and [math] is [math] -linked, where [math] is a parameter maximized over certain partitions of [math] . However, they do not discuss the calculation of [math] in their work. In this paper, we prove the exact value of [math] in the cases when [math] is a path, a cycle, a union of stars, a complete graph, and a complete bipartite graph. Several of these results lead to new degree-sum conditions for particular graph classes while others provide alternate proofs of previously known degree-sum conditions.

Submitted by Domingos Cardoso (dcardoso@ua.pt) on 2020-10-16T19:09:31Z No. of bitstreams: 1 Abreu2019_Article_SomeNewAspectsOfMainEigenvalue.pdf: 536479 bytes, checksum: cefc7b82af3b7fd8a76f302e07d5ed88 (MD5) Approved for entry into archive by Rita Gonçalves (ritaisabel@ua.pt) on 2020-10-19T16:31:02Z (GMT) No. of bitstreams: 1 Abreu2019_Article_SomeNewAspectsOfMainEigenvalue.pdf: 536479 bytes, checksum: cefc7b82af3b7fd8a76f302e07d5ed88 (MD5) Made available in DSpace on 2020-10-19T16:31:02Z (GMT). No. of bitstreams: 1 Abreu2019_Article_SomeNewAspectsOfMainEigenvalue.pdf: 536479 bytes, checksum: cefc7b82af3b7fd8a76f302e07d5ed88 (MD5) Previous issue date: 2020-03 published

Let G be a (p, q) graph. Let f : V (G) → {1, 2, . . . , k} be a map where k is an integer 2 ≤ k ≤ p. For each edge uv, assign the label |f (u) − f (v)|. f is called k-difference cordial labeling of G if |vf (i) − vf (j)| ≤ 1 and |ef (0) − ef (1)| ≤ 1 where vf (x) denotes the umber of vertices labelled with x, ef (1) and ef (0) respectively denote the number of edges labelled with 1 and not labelled with 1. A graph with a k-difference cordial labeling is called a k-difference cordial graph. In this paper we investigate 3-difference cordial labeling behavior of Tn ʘK1, Tn ʘ2K1, Tn ʘK2, A(Tn)ʘK1, A(Tn)ʘ 2K1, A(Tn) ʘ K2.

We consider the important generalisation of Ramsey numbers, namely on-line Ramsey numbers. It is easiest to understand them by considering a game between two players, a Builder and Painter, on an infinite set of vertices. In each round, the Builder joins two non-adjacent vertices with an edge, and the Painter colors the edge red or blue. An on-line Ramsey number r˜(G,H) is the minimum number of rounds it takes the Builder to force the Painter to create a red copy of graph G or a blue copy of graph H, assuming that both the Builder and Painter play perfectly. The Painter’s goal is to resist to do so for as long as possible. In this paper, we consider the case where G is a path P4 and H is a path P10 or P11.

Topological graph theory deals with embedding the graphs in Surfaces, and the graphs considered as a topological spaces. The concept topology extended to the topologized graph by the S1 space and the boundary of every vertex and edge. The space is S1 if every singleton in the topological space is either open or closed. Let G be a graph with n vertices and e edges and a topology defined on graph is called topologized graph if it satisfies the following: Every singleton is open or closed and For all x X, | ∂(x) |≤ 2, where ∂(x) is the boundary of a point x. This paper examines some results about the topological approach of the Complete Graph, Path, Circuit, Hamiltonian circuit and Hamiltonian path. And the results were generalized through this work.

International audience; A broadcast on a graph $G=(V,E)$ is a function $f: V\longrightarrow \{0,\ldots,\operatorname{diam}(G)\}$ such that $f(v)\leq e_G(v)$ for every vertex $v\in V$, where$\operatorname{diam}(G)$ denotes the diameter of $G$ and $e_G(v)$ the eccentricity of $v$ in $G$. The cost of such a broadcast is then the value $\sum_{v\in V}f(v)$.Various types of broadcast functions on graphs have been considered in the literature, in relation with domination, irredundence, independenceor packing, leading to the introduction of several broadcast numbers on graphs.In this paper, we determine these broadcast numbers for all paths and cycles, thus answering a questionraised in [D.~Ahmadi, G.H.~Fricke, C.~Schroeder, S.T.~Hedetniemi and R.C.~Laskar, Broadcast irredundance in graphs. {\it Congr. Numer.} 224 (2015), 17--31].

We obtain new polynomial kernels and compression algorithms for PATH COVER and CYCLE COVER, the well-known generalizations of the classical HAMILTONIAN PATH and HAMILTONIAN CYCLE problems. Our choice of parameterization is strongly influenced by the work of Biro, Hujter, and Tuza, who in 1992 introduced H-graphs, intersection graphs of connected subgraphs of a subdivision of a fixed (multi) graph H. In this work, we turn to proper H-graphs, where the containment relationship between the representations of the vertices is forbidden. As the treewidth of a graph measures how similar the graph is to a tree, the size of graph H is the parameter measuring the closeness of the graph to a proper interval graph. We prove the following results.- PATH COVER admits a kernel of size O(parallel to H parallel to(8)), that is, we design an algorithm that for an n-vertex graph G and an integer k >= 1, in time polynomial in n and parallel to H parallel to, outputs a graph G' of size O(parallel to H parallel to(8)) and k'- CYCLE COVER admits a compression of size O(parallel to H parallel to(10)) into another problem, called PRIZE COLLECTING CYCLE COVER, that is, we design an algorithm that, in time polynomial in n and parallel to H parallel to, outputs an equivalent instance of PRIZE COLLECTING CYCLE COVER of size O(parallel to H parallel to(10)).In all our algorithms we assume that a proper H-decomposition is given as a part of the input.

The set of permutations on a finite set can be given the lattice structure known as the weak Bruhat order. This lattice structure is generalized to the set of words on a fixed alphabet $\Sigma$ = {x,y,z,...}, where each letter has a fixed number of occurrences. These lattices are known as multinomial lattices and, when card($\Sigma$) = 2, as lattices of lattice paths. By interpreting the letters x, y, z, . . . as axes, these words can be interpreted as discrete increasing paths on a grid of a d-dimensional cube, with d = card($\Sigma$).We show how to extend this ordering to images of continuous monotone functions from the unit interval to a d-dimensional cube and prove that this ordering is a lattice, denoted by L(I^d). This construction relies on a few algebraic properties of the quantale of join-continuous functions from the unit interval of the reals to itself: it is cyclic $\star$-autonomous and it satisfies the mix rule.We investigate structural properties of these lattices, which are self-dual and not distributive. We characterize join-irreducible elements and show that these lattices are generated under infinite joins from their join-irreducible elements, they have no completely join-irreducible elements nor compact elements. We study then embeddings of the d-dimensional multinomial lattices into L(I^d). We show that these embeddings arise functorially from subdivisions of the unit interval and observe that L(I^d) is the Dedekind-MacNeille completion of the colimit of these embeddings. Yet, if we restrict to embeddings that take rational values and if d > 2, then every element of L(I^d) is only a join of meets of elements from the colimit of these embeddings., Comment: arXiv admin note: text overlap with arXiv:1807.06862

A star edge coloring of a graph G is a proper edge coloring without bichromatic paths and cycles of length four. In this paper, we obtain the star edge chromatic number of the corona product of path with cycle, path with wheel, path with helm and path with gear graphs, denoted by Pm ◦ Cn, Pm ◦ Wn, Pm ◦ Hn, Pm ◦ Gn respectively.

Let G = (V, E) be a connected graph and d(x, y) be the distance between the vertices x and y in G. A set of vertices W resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in W. A metric dimension of G is the minimum cardinality of a resolving set of G and is denoted by dim(G). In this paper, Cycle, Path, Harary graphs and their rooted product as well as their connectivity are studied and their metric dimension is calculated. It is proven that metric dimension of some graphs is unbounded while the other graphs are constant, having three or four dimensions in certain cases.