EuDML | Browse

The search session has expired. Please query the service again.

Items

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Displaying 21 – 40 of 103

Containers and wide diameters of $P_{3} (G)$

Daniela Ferrero, Manju K. Menon, A. Vijayakumar (2012)

Mathematica Bohemica

The $P_{3}$ intersection graph of a graph $G$ has for vertices all the induced paths of order 3 in $G$ . Two vertices in $P_{3} (G)$ are adjacent if the corresponding paths in $G$ are not disjoint. A $w$ -container between two different vertices $u$ and $v$ in a graph $G$ is a set of $w$ internally vertex disjoint paths between $u$ and $v$ . The length of a container is the length of the longest path in it. The $w$ -wide diameter of $G$ is the minimum number $l$ such that there is a $w$ -container of length at most $l$ between any pair of different...

Contractible edges in some $k$ -connected graphs

Yingqiu Yang, Liang Sun (2012)

Czechoslovak Mathematical Journal

An edge $e$ of a $k$ -connected graph $G$ is said to be $k$ -contractible (or simply contractible) if the graph obtained from $G$ by contracting $e$ (i.e., deleting $e$ and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still $k$ -connected. In 2002, Kawarabayashi proved that for any odd integer $k \geq 5$ , if $G$ is a $k$ -connected graph and $G$ contains no subgraph $D = K_{1} + (K_{2} \cup K_{1, 2})$ , then $G$ has a $k$ -contractible edge. In this paper, by generalizing this result, we prove that for any integer...

Counterexamples for properties of line graphs of graphs of diameter two

Harishchandra S. Ramane, Ivan Gutman (2010)

Kragujevac Journal of Mathematics

Degree polynomial for vertices in a graph and its behavior under graph operations

Reza Jafarpour-Golzari (2022)

Commentationes Mathematicae Universitatis Carolinae

We introduce a new concept namely the degree polynomial for the vertices of a simple graph. This notion leads to a concept, namely, the degree polynomial sequence which is stronger than the concept of degree sequence. After obtaining the degree polynomial sequence for some well-known graphs, we prove a theorem which gives a necessary condition for the realizability of a sequence of polynomials with positive integer coefficients. Also we calculate the degree polynomial for the vertices of the join,...

Distance independence in graphs

J. Louis Sewell, Peter J. Slater (2011)

Discussiones Mathematicae Graph Theory

For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number $β_{D} (G)$ is the maximum cardinality of a D-independent set. In particular, the independence number $β (G) = β_{1} (G)$ . Along with general results we consider, in particular, the odd-independence number $β_{O D D} (G)$ where ODD = 1,3,5,....

Distance Magic Cartesian Products of Graphs

Sylwia Cichacz, Dalibor Froncek, Elliot Krop, Christopher Raridan (2016)

Discussiones Mathematicae Graph Theory

A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ : V → {1, . . . , n} such that the weight of every vertex v, computed as the sum of the labels on the vertices in the open neighborhood of v, is a constant. In this paper, we show that hypercubes with dimension divisible by four are not distance magic. We also provide some positive results by proving necessary and sufficient conditions for the Cartesian product of certain complete multipartite graphs and the cycle on four...

Edge-Transitive Lexicographic and Cartesian Products

Wilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani (2016)

Discussiones Mathematicae Graph Theory

In this note connected, edge-transitive lexicographic and Cartesian products are characterized. For the lexicographic product G ◦ H of a connected graph G that is not complete by a graph H, we show that it is edge-transitive if and only if G is edge-transitive and H is edgeless. If the first factor of G ∘ H is non-trivial and complete, then G ∘ H is edge-transitive if and only if H is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao...

Factoring directed graphs with respect to the cardinal product in polynomial time II

Wilfried Imrich, Werner Klöckl (2010)

Discussiones Mathematicae Graph Theory

By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we weaken the...

Factorisation of snarks.

Chladný, Miroslav, Škoviera, Martin (2010)

The Electronic Journal of Combinatorics [electronic only]

Folding on the wedge sum of graphs and their fundamental group.

Abu-Saleem, M. (2010)

APPS. Applied Sciences

Frucht’s Theorem for the Digraph Factorial

Richard H. Hammack (2013)

Discussiones Mathematicae Graph Theory

To every graph (or digraph) A, there is an associated automorphism group Aut(A). Frucht’s theorem asserts the converse association; that for any finite group G there is a graph (or digraph) A for which Aut(A) ∼= G. A new operation on digraphs was introduced recently as an aid in solving certain questions regarding cancellation over the direct product of digraphs. Given a digraph A, its factorial A! is certain digraph whose vertex set is the permutations of V (A). The arc set E(A!) forms a group,...

Fundamental groupoids of digraphs and graphs

Alexander Grigor'yan, Rolando Jimenez, Yuri Muranov (2018)

Czechoslovak Mathematical Journal

We introduce the notion of fundamental groupoid of a digraph and prove its basic properties. In particular, we obtain a product theorem and an analogue of the Van Kampen theorem. Considering the category of (undirected) graphs as the full subcategory of digraphs, we transfer the results to the category of graphs. As a corollary we obtain the corresponding results for the fundamental groups of digraphs and graphs. We give an application to graph coloring.

Game chromatic number of Cartesian product graphs.

Bartnicki, T., Bresar, B., Grytczuk, J., Kovse, M., Miechowicz, Z., Peterin, I. (2008)

The Electronic Journal of Combinatorics [electronic only]

Generalized 3-edge-connectivity of Cartesian product graphs

Yuefang Sun (2015)

Czechoslovak Mathematical Journal

The generalized $k$ -connectivity $κ_{k} (G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$ -edge-connectivity which is defined as $λ_{k} (G) = min {λ (S) : S \subseteq V (G)$ and $| S | = k}$ , where $λ (S)$ denotes the maximum number $ℓ$ of pairwise edge-disjoint trees $T_{1}, T_{2}, ..., T_{ℓ}$ in $G$ such that $S \subseteq V (T_{i})$ for $1 \leq i \leq ℓ$ . In this paper we prove that for any two connected graphs $G$ and $H$ we have $λ_{3} (G □ H) \geq λ_{3} (G) + λ_{3} (H)$ , where $G □ H$ is the Cartesian product of $G$ and $H$ . Moreover, the bound is sharp. We also obtain the...

Generalized outerplanar index of a graph

Zahra Barati (2018)

Czechoslovak Mathematical Journal

We define the generalized outerplanar index of a graph and give a full characterization of graphs with respect to this index.

Graph products and new solutions to Oberwolfach problems.

Rinaldi, Gloria, Traetta, Tommaso (2011)

The Electronic Journal of Combinatorics [electronic only]

Graphs with least eigenvalue -2 attaining a convex quadratic upper bound for the stability number

D. M. Cardoso, D. Cvetković (2006)

Bulletin, Classe des Sciences Mathématiques et Naturelles, Sciences mathématiques

Harary Index of Product Graphs

K. Pattabiraman, P. Paulraja (2015)

Discussiones Mathematicae Graph Theory

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. In this paper, the exact formulae for the Harary indices of tensor product G × Km0,m1,...,mr−1 and the strong product G⊠Km0,m1,...,mr−1 , where Km0,m1,...,mr−1 is the complete multipartite graph with partite sets of sizes m0,m1, . . . ,mr−1 are obtained. Also upper bounds for the Harary indices of tensor and strong products of graphs are estabilished. Finally, the exact formula...

Identifying codes of Cartesian product of two cliques of the same size.

Gravier, S., Moncel, J., Semri, A. (2008)

The Electronic Journal of Combinatorics [electronic only]

Interval edge colorings of some products of graphs

Petros A. Petrosyan (2011)

Discussiones Mathematicae Graph Theory

An edge coloring of a graph G with colors 1,2,...,t is called an interval t-coloring if for each i ∈ {1,2,...,t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. A graph G is interval colorable, if there is an integer t ≥ 1 for which G has an interval t-coloring. Let ℜ be the set of all interval colorable graphs. In 2004 Kubale and Giaro showed that if G,H ∈ 𝔑, then the Cartesian product of these graphs...

Currently displaying 21 – 40 of 103

Previous Page 2 Next